Na místě dnešního chrámu stál v Bohuticích farní kostel již v polovině 13. století. V raném novověku, konkrétně v roce 1615, postavil Vilém Kusý pro své nekatolické poddané za vsí kostel Všem Andělům, jenž byl po zrušení Jezuitského řádu v roce 1773 odsvěcen a později zbořen. Obec se tak ocitla bez vlastní sakrální stavby a věřící museli jezdit na mše do Olbramovic.

Zásadní obrat přišel se Josefem Sedelem, majitelem tamního statku. Po smrti svých dvou dětí v letech 1834 a 1846 se rozhodl zřídit farní nadaci s kapitálem 16 300 rakouských zlatých, jejíž úroky měly zajistit provoz fary, kostela a kapli. Od roku 1864 se Seydel sám zabýval stavbou nového kostela – věnoval stavební místo i prostředky na jeho výstavbu. Rozhodnutím biskupské konzistoře v Brně byla 15. ledna 1867 zřízena samostatná farnost v Bohuticích. O čtyři měsíce později, 11. května 1867, byl slavnostně položen základní kámen. Mezi pozvanými hosty byl i František Sušil, moravský národní buditel a sběratel národních písní. Seydel se nemohl osobně zúčastnit, protože jeho manželka byla vážně nemocná, ale oba přišli na slavnostní mši a průvod k základům 4. října.

Prvním architektem kostela byl mikulovský inženýr Antonín Tater, kterého brzy nahradil stavitel Florián Zedník, poté co byl Tater odvolán do Moravské Třebové. Stavba se prodražovala – pracovníci odcházeli na stavbu železniční tratě, kde si vydělali více, a objevily se také závady na střeše, které vedly k dlouhému soudnímu sporu mezi Seydelem a stavitelem. Přes překážky se práce ubíraly kupředu. Osmého srpna 1869 v den Nanebevzetí Panny Marie byl na vrchol věže upevněn kříž, a během podzimu byla stavba hotova. Na svátku svaté Kateřiny Alexandrijské (25. listopadu) byly přivezeny čtyři posvěcené zvony z brněnského Petrova.

Před vysvěcením se však objevily potíže. Seydel v kostele nechal bez úředního povolení pochovat tělo své zesnulé manželky, kterou později nechal exhumovat a převézt z hrobky v kaple. Úřady následně zakázaly užívání a vysvěcení kostela. Spor urovnal až moravský biskup Karel Nöttig, který přijel do Bohutic 7. září 1873. Den poté posvětil kříž a předal klíč faráři P. Rudolfu Scholzovi. Kostel byl následně vysvěcen a sloužila se pontifikální mše svatá. Budova se stala vedle zámku hlavní dominantou obce.

V roce 1906 nechal farář Karel Bezstarosti opravit vnitřní malby a v roce 1928 byla při 70. výročí lurdských zjevení vybudována lurdská jeskyně se sochou Panny Marie z Lyonu a oltářem z kararského mramoru. Ve třicátých letech se tu odehrávaly rozsáhlé poutě za účasti tisíců poutníků – poutní tradice měla v Bohuticích kořeny již od 17. století. V roce 1971 byly zjištěny statické poruchy, kterým se čelilo až v roce 1984 generální opravou stavby. Od té doby slouží věřícím i návštěvníkům.