A veszprémi káptalan egyik oklevele 1247-ben említi elsőként az épülő templomot. Ezért következtetnek a kutatók arra, hogy a templom alapítása és építésének kezdete 1246-ra vagy 1247-re tehető.

A templom első ismert plébánosa, Keresztély ekkor kezdte meg működését a budaújhegyi Mária-egyházban.  Egészen 1272-ig volt a templom plébánosa.

I. Anjou Károlyt, ismertebb nevén Károly Róbertet 1309. június 15-én egy alkalmi koronával a templomban koronázták meg.

A húsvét előtti 8. vasárnapon, 1384. február 14-én a templom déli tornya leomlott mise közben. Eberhard Windecke emlékirata beszámolt arról is, hogy a szerencsétlenségben nem sérült meg senki.

A toronyomlás után a XIV. század végétől kezdve jelentősen átalakították a templomot. Az építkezések sokáig elhúzódtak, mert a munkálatok támogatására 1414-ben adtak ki egy pápai búcsúlevelet. A mellékhajók boltozatának megemelésével csarnokteret hoztak létre, és Zsigmond király uralkodása idején a mellékhajók szentélyét is meghosszabbították, sokszögzáródású terekké alakították.

A templom két oldalán 1433-ra elkészült a Garai család Mindenszentek-kápolnája és Johann Ellenpeck budai polgár sírkápolnája.

Hunyadi Mátyás királlyá választása után ünnepélyes, hálaadó szentmisén vett részt a templomban. Az 1458–1490 között uralkodó király több szállal kötődött a templomhoz.

1463. május 1-jén Mátyás király itt vette feleségül a cseh király lányát, Podjebrád Katalint.

A XV. század elején megkezdett toronyépítési munkálatok befejeződtek. Mátyás király címerét elhelyeztette a torony délnyugati falán.

A hamar megözvegyült uralkodó, Hunyadi Mátyás második feleségét Aragóniai Beatrixot is a Nagyboldogasszony-templomban vette el 1476 decemberében.

II. Ulászló király egy Madonna-szobrot ajándékozott a templomnak hálából, mert megmenekült az ellene tervezett merénylettől.

Szulejmán szultán elfoglalta Budát. A Nagyboldogasszony-templomot, a város főtemplomát dzsámivá alakították.

Buda várát 1686. szeptember 2-án a szövetséges keresztény csapatok, Lotharingiai Károly és Miksa bajor herceg vezetésével a Szent Liga szerezte vissza.

A templomot igazgató jezsuita rend 1688-tól építkezésbe kezdett a templom mellett. Északról kollégiumot, délről szemináriumot kapcsoltak a templomhoz.

1723-ban Buda városában óriási tűzvész pusztított, a templom és a mellette álló épületek is súlyos károkat szenvedtek.

XIV. Kelemen pápa feloszlatta a jezsuita rendet. Ettől kezdve a templom Buda városának fennhatósága, kegyurasága alá került.

A szentély alatt temetkező kápolnát alakítottak ki a Zichy család számára.

1785. november 15-én elárverezték a Budavári Nagyboldogasszony-templom középkori és jezsuita korszakból származó kincseinek jelentős részét.

1810-re elkészült a templom toronyórája.

A torony ércsisakját – rossz állapota miatt – egyszerű zsindelytetőre cserélték ki.

A Kiegyezési törvények aláírása után, 1867. június 8-án a templomban koronázták magyar királlyá és királynévá Ferenc József osztrák császárt és feleségét, Erzsébetet.

Schulek Frigyes vezetésével megkezdődött a templom helyreállítása.

1896. augusztus 15-én szentelte fel Vaszary Kolos hercegprímás a felújított épületet.

III. Béla király és felesége, Anne de Châtillon földi maradványait ünnepélyesen újratemették a templom Szentháromság-kápolnájában.

Ferenc József magyar királlyá koronázásának 40. évfordulóján adományt tett, ebből készült el a templom új orgonája, a „Király orgonája”.

Boldog IV. Károlyt és feleségét Bourbon-Pármai Zitát 1916. december 30-án koronázták meg a templomban. Ez volt az utolsó magyar királykoronázás.

Schulek János vezetésével 1933–1944 között ismét restaurálták a templomot.

A XXXIV. Nemzetközi Eucharisztikus Kongresszus alkalmával 1938. május 23-án Serédi Jusztinián hercegprímás a Budavári Főtemplomban köszöntötte Eugenio Pacelli pápai legátust, a későbbi XII. Piusz pápát.

A II. világháborúban, Budapest ostromakor a templom súlyosan megsérült

A Mátyás-templom egyházművészeti gyűjteményének bemutatására Tóth János plébános múzeumot hozott létre a templomban.

Magyarországi apostoli látogatása alkalmával, 1991. augusztus 19-én Szent II. János Pál pápa a templomban beszédet intézett a kispapokhoz és szerzetesnövendékekhez, és együtt imádkozott velük.

Az altemplom keleti bejáratánál július 23-án hajnalban pokolgép robbant. A helyreállítás és restaurálás munkálatait közadakozásból tudták finanszírozni.

A templom hívei gyalogos zarándoklaton hozták haza Rómából azt a koronamásolatot, melyet Szent II. János Pál pápa megáldott, és ezzel koronázták meg az államalapítás emlékére 2000. augusztus 15-én a főoltár Szűzanya szobrát.

2004–2013 között ismét teljesen felújították a templomot.

A meglévő két történelmi harang mellé 2010–2011 között négy új harangot öntöttek.