Enoladijska romanska cerkev je bila zgrajena v 12. stoletju. Vse kaže, da je bila to prva mariborska župnijska cerkev, ki je prvotno imela dolgo pravokotno ladjo in ožji pravokotni prezbiterij. V času, ko je Maribor postal mesto, torej okoli sredine 13. stoletja, so zgradili novo, večjo triladijsko cerkev – današnjo stolnico na Slomškovem trgu – in staro župnijsko cerkev prepustili minoritom, krščanskemu verskemu redu, ki ga je leta 1209 ustanovil Frančišek Asiški.
Minoriti so staro cerkev temeljito prenovili in jo posvetili sv. Mariji Vnebovzeti oziroma Naši ljubi Gospe. Cerkev je takrat dobila zgodnjegotsko podobo, pravokotni prezbiterij so nadomestili s petosminsko zaključenim dolgim korom. Romanska cerkev je dobila tudi nov glavni portal, ki so ga zaradi mestnega obzidja na zahodu postavili sredi njene severne fasade.
Cerkev je kasneje doživela še več prezidav. Najobsežnejša sega v čas okoli leta 1710, ko je dobila današnjo baročno podobo. Podrli so prezbiterij na vzhodu in zgradili novega na zahodu. Na vzhodu so dodali zvonik s čebulasto streho, na jugu pa močno obokano zakristijo. V notranjščini so srednjeveško ladjo v celoti obokali. Pod tlemi vzhodnega dela so uredili banjasto obokano grobnico.
Po letu 1747, ko so v cerkev prenesli Marijino skulpturo iz Konjic, je postala pomembno romarsko središče. Prav to je bil povod za ponovno prenovo, in sicer je cerkev leta 1770 dobila novo, sedanjo vzvalovano pilastrsko fasado, prezbiterij pa bogato štukaturo in poslikavo, katere avtor je slikar Joseph M. Göbler.
Med jožefinskimi reformami so leta 1784 cerkev in samostan odvzeli minoritom ter ju namenili potrebam vojske. Cerkev je takrat izgubila vse oltarje, orgle, pevski kor in zgornjo polovico zvonika. Kot vojaško skladišče so jo uporabljali do leta 1927, nato je bilo v njej do leta 1990 civilno skladišče. Od takrat je nekaj let služila kot gledališko prizorišče.
