Bazylikę Mariacką zaczęto wznosić pod koniec XIII w. na fundamentach wcześniejszego kościoła romańskiego. Nowa świątynia została konsekrowana ok. 1320 r. Przez kolejne stulecia kościół był wielokrotnie przebudowywany, zmianom podlegały zarówno bryła, jak i wnętrze.
W drugiej połowie XIV w. powstało wydłużone jednonawowe prezbiterium przykryte sklepieniem gwiaździstym. Światło wpada do wnętrze przez wysokie okna z witrażami. Średniowieczne witraże zachowały się tylko w trzech oknach; pozostałe pochodzą z XIX w., a wykonane zostały m.in. przez Stanisława Wyspiańskiego i Józefa Mahoffera.
Po obu stronach prezbiterium ustawiono w XVI w. nakryte baldachimami stalle, do których wiek później dodano płaskorzeźbione zaplecki ze scenami z życia Chrystusa i Marii.
Lata 1477–1489 przyniosły świątyni ołtarz główny dłuta Wita Stwosza, uważany za arcydzieło rzeźbiarskie późnego gotyku. Pod koniec XIV stulecia kościół przybrał formę bazyliki z nawą główną wyższą od naw bocznych, a korpus przykryto sklepieniem krzyżowo-żebrowym. Wieża północna została podwyższona i przystosowana do pełnienia funkcji strażnicy miejskiej. W 1478 r. Maciej Heringk nakrył wieżę charakterystycznym wielobocznym hełmem, który w 1666 r. został ozdobiony złoconą koroną maryjną.
XVIII w. przyniósł decyzję o wprowadzeniu do wnętrza kościoła estetyki barokowej. Pracami kierował Franciszek Placidi. To jego autorstwa jest prowadząca do kościoła barokowa kruchta wybudowana w połowie XVIII w. Jej wieloboczna forma architektoniczna zwieńczona ażurową wieżyczką naśladuje kaplicę Grobu Pańskiego w Jerozolimie. Drewniane drzwi do kruchty zdobią rzeźbione głowy proroków, apostołów i polskich świętych wykonane w 1929 r. przez Karola Hukana.
W 1795 r. zlikwidowano przykościelny cmentarz, a pozyskany w ten sposób teren od tej pory znany jest jako Plac Mariacki. Część epitafiów z terenu cmentarza została wmurowana w ściany kościoła.
Pod kierunkiem Tadeusza Stryjeńskiego przeprowadzono u schyłku XIX w. kompleksową restaurację świątyni. Kościół Mariacki zyskał wtedy m.in. nową dekorację malarską projektu Jana Matejki, przy wykonaniu której pracowali m.in. Stanisław Wyspiański i Józef Mehoffer. Sklepienie imituje gwiaździste niebo, a ściany pokryte są malowidłami z motywami ornamentalnymi, heraldycznymi, tekstami modlitw maryjnych i postaciami aniołów grających na instrumentach lub trzymających banderole z tekstem Litanii Loretańskiej.