Kostel Nanebevzetí Panny Marie byl vystavěn piaristy na místě původního kostela Panny Marie Českých bratří, kteří ve Strážnici působili v době, kdy strážnické panství vlastnili Žerotínové.Stavba nového kostela byla započata 25. srpna 1742. Starý kostel byl z vnější strany obezdíván novým zdivem, takže bohoslužby ve staém kostele nebyly novou výstavbou příliš ovlivňovány.
Kdo byl autorem nového díla se přesně neví. Předpokládá se, že architektem a stavitelem kostela byl italský barokní stavitel Ignác Cyrani. Dílo bylo financováno převážně Magnisy, tehdejšími švédskými majiteli strážnického panství. Na výstavbu kostela však přispívali i další páni z okolních měst. Pro práci byli uvolňováni robotní sedláci, vyplácení strážnickou obcí. Piaristé získali povolení vybírat dary pro podporu výstavby v okruhu 12 mil.

Stavba nového kostela probíhala celkem rychle. Na podzim roku 1743 byl dokončen presbytář. V roce 1744 dokončil mistr Michal Holešovský střechu a 17. června 1745 bylo dokončeno zaklenutí kostela. V tomto roce byla také postavena i první kostelní věž a na její báň byl umístěn posvěcený kříž. Pod kříž byla vložena pamětní listina s ostatky svatých.

Stavební práce byly dokončeny v roce 1746. Vznikl nový jednolodní kostel se dvěma čtvercovými věžemi v průčelí, s hlavním vchodem uprstřed průčelí a se dvěma bočními vchody pod věžemi. K jižní straně presbytáře přiléhá kaple, na jeho severní straně je sakristie. Nad kaplí i sakristií byly vytvořeny oratoře. Pod kostelem byla vyhloubena krypta pro hroby a pro dvě schrány kostí.
Zvony byly přeneseny ze staré věže původního kostela v roce 1745. Z děla, které piaristé dostali ze zámku, byl přelit další zvon. Čtvrtý zvon dal zhotovit Václav Ertl. Výzdoba interiéru kostela byla prováděna od roku 1745. V lodi kostela byl vytvořen hlavní oltář a šest oltářů vedleších.