Základní kámen byl položen 9.6. 1745 prelátem ze Šternberka. První přípravy ke stavbě byly vedeny děkanem Josefem Baptistem, který přišel do Budišova 30.4. 1746.

Stavba byla realizována pod zvláštní patronací a finanční pomoci kardinála Ferdinanda Julia, hraběte Troyer.

Stavba trvala do roku 1755. Dokončena byla během působení děkana Johanna Franze Neumanna, který k nám přišel z Oder a byl také městským rychtářem. Vypráví se, že nad domy vedla z náměstí ke stavbě kostela stezka z desek a že tkalci vždy večer dopravili tolik cihel na lešení, aby jich bylo dost na celodenní stavbu. Jako dík dostali tkalci k užívání kůr do té doby, než jim byl odebrán „pro páchání nepravostí“.

12. dubna 1756 byl kostel zasvěcen Nanebevzetí Panny Marie a patronem byl olomoucký biskup. První varhany postavil r. 1758 Josef Georg Schwarz z Libavé. Měly 19 registrů, z toho 9 manuálových, 6 positivových a 4 pedálové. Křížová cesta byla dokončena roku 1763. Na věžích bylo 5 zvonů. Nejtěžší vážil 616 kg, nejmenší umíráček 83 kg.

Kronika neříká nic o tom, kolik věnovali obyvatelé Budišova finančních prostředků na stavbu kostela, jsou zdůrazňována jen některá jména, dary, jako financování celého elektrického osvětlení, darování ručně vázaného koberce k hlavnímu oltáři (oltářů je 7), darování bohatě zlatem vyšívaných rouch.

Varhany byly přestavěny roku 1930 firmou Rieger z Krnova. Působil zde i velmi dobrý pěvecký sbor, byly tu pořádány koncerty. Teprve v červnu 1912 byly dokončeny věže, které při stavbě z nedostatku peněz byly pouze nouzově zastřešeny. V roce 1893 byla vytvořena nadace a začaly se shromažďovat finanční prostředky. Mnoho občanů ve své závěti odkázalo značnou částku na dokončení věží.