Nejstarším chrámem na Starém Brně byla rotunda, skládající se z válcové lodi a apsidy mírně podkovovitého půdorysu, dle archeologů postavená kolem roku 1000. V průběhu 12. století byla původní rotunda nahrazena rozsáhlejší jednolodní románskou stavbou se čtvercovou apsidou, ke které se vztahuje první písemná zpráva z roku 1210, kde se již hovoří o existenci kostela P. Marie na Starém Brně. Ale i tento kostel krátce po roku 1300 nahradil gotický farní chrám na půdorysu latinského kříže s trojbokým závěrem.
Vedle něj založila 15. května 1323 královna Eliška Rejčka, vdova po dvou českých králích, Václavu II. a Rudolfu Habsburském, klášter cisterciaček. Klášter pojmenovala Aula Sanctae Mariae. Král Jan Lucemburský se stal jeho spoluzakladatelem. Dalším příznivcem byl moravský zemský hejtman Jindřich z Lipé. Brzy po založení starobrněnského kláštera královnou Eliškou Rejčkou se začalo i se stavbou nového klášterního kostela. Když v roce 1329 Jindřich z Lipé zemřel, byl pohřben v místě pravé, ještě nedostavěné, lodi nově budovaného kostela. Od roku 1332 Eliška Rejčka již patrně trvale žije v klášteře, u něhož byl v roce 1333 založen špitál pro 8 nemocných laiků, 8 přestárlých kněží a 1 jáhna. Podstatná část nového chrámu byla již pravděpodobně hotova tak, aby v něm mohly probíhat bohoslužby, protože se původní kostel Panny Marie začal užívat jako špitální kaple a jeho patrocinium Panny Marie bylo přeneseno na nový klášterní kostel. Špitální kostel byl zasvěcen sv. Anně.
V roce 1335 umírá zakladatelka kláštera a nového chrámu Eliška Rejčka. Je pohřbena v průsečíku hlavní a příčné lodi před hlavním oltářem. Toto místo je označeno na dlažbě její iniciálou E.
Zakladatelka zanechává po sobě gotický chrám s bohatostí architektonických prvků. Okenní kružby jsou v českých zemích jedny z nejbohatších a celý chrám působí dynamikou a odhmotněním. Chrám Nanebevzetí Panny Marie je označován jako perla gotické architektury na Moravě. Mohutná stavba byla postavena na složitém půdoryse trojlodního chrámu, zakončeném trojlistým závěrem a mohutně vyvinutou příčnou lodí. Samotná stavba je oproti zvyklostem své doby postavena z pálených cihel. Kámen je použit jen na sloupy a žebra kleneb. Použití pálených cihel je charakteristickým znakem chrámu – i fasáda je z režného zdiva. Nejstarší stavební části kláštera jsou kromě chrámu ještě přilehlé budovy staré sakristie, 3. nádvoří, tzv. Rajský dvůr s křížovou chodbou a nedílnou součástí kláštera – Kapitulní síní.
Na další vývoj chrámu a kláštera měly vliv dějiny. Roku 1421 a 1428 byl klášter vypleněn a vypálen husity, ještě větší škody byly napáchány v roce 1467, kdy vojska krále Jiřího z Poděbrad zpustošila klášter při obléhání Brna. Devastace a následné opravy byly tak rozsáhlé, že roku 1470 muselo dojít k novému vysvěcení chrámu. Největší škody utrpěla hlavně obytná část kláštera, zvláště pak křížová chodba. Další destrukce se opakovaly v průběhu 17. století, kdy Brno obléhala švédská vojska. Po skončení třicetileté války vybudovaly cisterciačky „nový klášter“ na západní straně. Šlo o jednopatrovou budovu obklopující nepravidelný čtyřúhelníkový dvůr. Následně byl v patře vybudován dormitář, ložnice sester, těsně přiléhající ke kostelu. Z dormitáře se vstupovalo přímo na chór sester v kostele.
Do posledních stavebních úprav cisterciaček patří budova tehdejšího proboštství od Mořice Girmma, postavená ještě před rokem 1737, tedy již v barokním slohu.
Koncem 17. století byla do severního ramene velké příční lodi postavena barokní hudební kruchta – figurální kůr, dnes zvaný malý kůr. Počátkem šedesátých let 18. století přistoupily pak cisterciačky k úplné modernizaci chrámového vybavení. Koncipoval je a na jeho tvorbě se zásadním způsobem podílel brněnský sochař Ondřej Schweigl. Ten vybudoval v letech 1762-1765 v závěru kněžiště hlavní oltář s monumentálním sloupovým retabulem: z mramorového podstavce se zvedá zděná kulisa opatřená umělým mramorem se sochami světců.
Rovněž boční oltáře u pilířů v malé příčné lodi, ve velké příčné lodi a mezi hlavní lodí a bočními kaplemi vytvořil opět Ondřej Schweigl či někdo ze Schweiglovy dílny.
Dílem Ondřeje Schweigla je také kazatelna, přístupná po schodišti točícím se kolem pilíře. Ve výplních na parapetu schodiště i řečniště jsou řezané reliéfy znázorňující epizody z návratu Židů z egyptského zajetí. Na pozadí řečniště je reliéf Vztyčení měděného hada na poušti, na stříšce přijímá Mojžíš desky Desatera.
Poslední stavební úpravy cisterciaček, které sídlily na Starém Brně 459 let, se týkají kaple Božího hrobu (dnešní kaple Pražského Jezulátka) a úpravy podkruchtí pod malým kůrem, kde byl zbudován oltář Panny Marie Bolestné se sochou Piety. Tuto sochu zhotovil Ondřej Schweigl ale již po příchodu augustiniánů na Staré Brno.
Nástup Josefa II. na císařský trůn znamenal i nástup jeho josefínských reforem, týkajících se hlavně omezení vlivu církve, zrušení procesí, mnoha poutních míst a také mnoha církevních řádů. 18. března 1782 tak Josef II. ruší i komunitu cisterciaček na Starém Brně a následující rok přikázal augustiniánům, do té doby sídlícím v klášteře při kostele sv. Tomáše, přesídlit do opuštěných prostor na Starém Brně, aby mohl jejich klášter zabrat pro státní úřady. Augustiniánům však bývalý cisterciácký klášter prostorově nevyhovoval a bylo nutné provést potřebné přestavby. Mimo jiné se projevila nutnost přizpůsobit nové sídlo některým náročným částem výbavy, kterou si přinesli s sebou. Šlo o zařízení sakristií, především pak o knihovnu s nádhernými regály a alegorickými figurami, vyrobenou klášterní dílnou, vedenou uměleckým truhlářem Bernardem Stettnerem. Nezbývalo, než pro ni vybudovat zvláštní sál. Tak došlo ke zboření kostela sv. Anny s přilehlým špitálem. Na jeho místě vystavěl Jan Amon podle projektu z roku 1796 budovu s novým refektářem v přízemí a s knihovním sálem v 1. patře, z hřebene jeho střechy vyrůstá hodinová vížka, datovaná 1805.
Do starobrněnského chrámu si augustiniáni v roce 1783 přestěhovali i stříbrný oltář s obrazem Panny Marie Svatotomské. Tento oltář doposud sídlil v boční kapli kostela sv. Tomáše. Díky josefínským reformám se tak stříbrný oltář s obrazem stává hlavním oltářem mariánského chrámu na Starém Brně a vytvořil tak působivou dominantu chrámu. Stříbrný oltář je dílem augsburského zlatníka Johanna Gregora Herkommera a byl vytvořen v letech 1735-1736. Nad stříbrným svatostánkem – tabernáklem je zasazen v baldachýnovém retabulu rám s obrazem Madony s dítětem - „Palladium města Brna“, jehož vznik se datuje pravděpodobně do poloviny 13. století.
V kostele pak koncem 18. století proběhlo několik dalších stavebních úprav. Jan Amon nechal zazdít arkády mezi hlavní a boční lodí v zadní části, čímž vznikly nové sakristie a depozitář. Dále dal vybourat chór sester – velký kůr, tehdy zasahující až do velké příčné lodi a nechal zbudovat nový mělký hudební kůr.
Další zásahy spadají až do konce 19. století, kdy August Prokop, stavitel brněnského dómu, navrhl novogotické úpravy jižního vstupního portálu. Nad vchod umístil do tympanonu sousoší Korunování Panny Marie. Nad kaplí sv. Augustina, která vznikla částečným zazděním původní gotické křížové chodby ze 14. století, nechal vybudovat oratoř. Roku 1901 dle projektu Richarda Jordana byla zbourána mělká hudební kruchta a byla nahrazena nynějším novogotickým útvarem, tedy poněkud zkrácenou rekonstrukcí původního chóru sester. Pod touto novogotickou kruchtou, v nynější Křížové kapli, se nachází od roku 1903 soubor čtrnácti zastavení křížové cesty z roku 1890 od Johanna Grissemanna z Instu, tyto dřevořezby byly původně umístěné na bočních stěnách v zadní části kostela.
Současná výmalba chrámu dle návrhu Richarda Völkela pochází z let 1899-1902, ornamentální výzdobu provedenou pomocí šablon provedl dvorní dekorační malíř Josef Kott z Vídně. V roce 1902 byla rovněž provedena instalace elektrického osvětlení kostela firmou Bartelmus, Donát a spol.
Mimořádný význam chrámu Panny Marie na Starém Brně byl potvrzen papežem Janem Pavlem II., který mu udělil 6. října 1987 titul „Basilica Minor“. Tímto rozhodnutím papež ukázal na duchovní bohatství a neustále tryskající pramen Božích milostí na tomto místě a stal se po Velehradu a sv. Hostýnu teprve třetí bazilikou na Moravě. Tento titul následně obdržely na Moravě i bazilika na sv. Kopečku u Olomouce, mariánský chrám ve Frýdku a ve Žďáře nad Sázavou.
Od roku 1990 probíhá obnova augustiniánského opatství. Klášterní budovy i bazilika prošly velkými opravami včetně restaurování stříbrného oltáře.
