Árið 1859 komu fyrstu kaþólsku prestarnir hingað til lands eftir siðaskiptin. Það voru þeir Bernard Bernard og Jean-Baptiste Baudoin og keyptu þeir jörðina Landakot við Reykjavík og settust þar að. Faðir Baudoin reisti litla kapellu við þetta hús 1864. Hún var síðar leyst af hólmi af timburkirkju við Túngötu, nálægt prestsetrinu. Þessi kirkja var helguð heilögu hjarta Jesú.
Eftir fyrri heimsstyrjöldina hófu Montfortprestar, sem höfðu tekið við trúboðinu í Íslandi árið 1903, að leggja drög að byggingu nýrrar kirkju. Ýmsar teikningar voru gerðar en loks var ákveðið að smíða kirkju í nýgotneskum stíl. Hornsteinninn var lagður 1927. Árið 1929 var kirkjan fullreist.
Guðjóni Samúelssyni, húsameistara ríkisins, var falið að teikna kirkjuna. Sameinaði hann í teikningum sínum gotneskan stíl við séríslensk einkenni, og má einkum greina það í ytri burðarsúlum kirkjunnar, sem minna á stuðlaberg í fjallshlíð. „Landakotskirkja sýnir að enn má yrkja í stein, og að Íslendingar hafa nokkuð fram að leggja í þeirri grein hinna fögru lista,“ sagði Jónas Jónsson frá Hriflu í grein í jólablaði Tímans árið 1927. Jens Eyjólfsson, byggingameistari bæjarins, sá um að reisa kirkjuna. Breyttist hún nokkuð í meðförum hans, og var til dæmis hætt við að reisa turnspíru ofan á turn kirkjunnar.
Lengi var hún stærsta kirkja landsins. Kirkjan var vígð þann 23. júlí 1929. Það gerði sérstakur sendimaður Píusar XI, William kardínáli van Rossum CssR, yfirmaður stjórnardeildar Páfagarðs "De Propaganda Fide". Kardínálinn kom til Íslands til að lýsa yfir stofnun postullegrar trúboðskirkju á Íslandi og til að vígja til biskups postullegan stjórnanda hennar, Martein Meulenberg.
Athöfnin hófst klukkan hálfníu um morguninn á því að Willem van Rossum kardínáli, og einn helsti hvatamaður að hinni nýju kirkju, gekk til gömlu kirkjunnar, og var þar haldin stutt messa. Að því loknu voru helgir dómar kirkjunnar bornir úr gömlu kirkjunni og yfir í þá nýju. Meulenberg, sem nú var prefekt kirkjunnar, gekk með helgidómana einn hring í kringum kirkjuna og fylgdi skrúðfylking á eftir. Þegar inn í hina nýju kirkju var komið var altarið vígt.
Í kjölfarið fylgdu ýmsar helgiathafnir sem kardínálinn v. Rossum framkvæmdi, ásamt prestum kirkjunnar og fylgdarliði sínu. Að vígslu lokinni var haldin messa. Messugerðinni lauk á því að kardínálinn söng Te Deum úr hásæti sínu, en söfnuður og aðkomufólk stóð upp. „Gengu klerkar síðan með kórdrengjum fyrir í skrúðgöngu úr kirkjunni.“
Dómkirkjan ber nafn Krists konungs í heiðursskyni við Krist, Drottin alheimsins. Kirkjan er undir verndarvæng hinnar sælu Maríu meyjar Guðsmóður, sankti Jósefs og tveggja helgra, íslenskra manna, Jóns Ögmundarsonar og Þorláks Þórhallssonar. Kirkjuklukkurnar þrjár eru tileinkaðar Kristi konungi, Maríu mey og heilögum Jósef.
Árið 1956 var sett upp orgel í kirkjunni sem smíðað var hjá Fröbenius-smiðjunni í Kaupmannahöfn. Kirkjan og orgelið hafa verið endurnýjuð nokkrum sinnum, síðast 1999-2000.
Á hægri hlið við innganginn í kirkjuna stendur tréstytta frá miðöldum af Maríu mey með barninu. Talið er að hún sé frá 14. öld. Líklega var hún í sveitakirkju á árum áður en eftir siðaskiptin tók bóndinn á Reykhólum hana í hús sitt. Hún var gefin Landakotskirkju árið 1926 og þar er hún tignuð sem „Reykhóla-María“. Jóhannes Páll páfi II krýndi styttuna þegar hann heimsótti Ísland í júní 1989.
Í tilefni af hátíðinni „Kristni í 1000 ára á Íslandi“ var dómkirkjan heiðruð og fengin nafnbótin „basilika“, hin eina í löndum Norður-Evrópu. Hinn 1. júlí 2000 lýsti Edward Idris Cassidy kardínáli þessari nafngjöf yfir við hátíðlega messu í dómkirkjunni.
Til hægri fyrir dyrum úti er brjóstmynd af Marteini Meulenberg biskupi (1872-1941) en hann stóð fyrir byggingu kirkjunnar. Hann var fyrsti kaþólski biskupinn á Íslandi eftir siðaskiptin.
Til vinstri við kirkjuna var þann 17. september 2000 afhjúpuð stytta af konu og nefndist hún „Köllun“. Hana gerði listakonan Steinunn Þórarinsdóttir til minningar um mannúðarstörf Jósefssystra sem störfuðu á Íslandi í meira en eina öld.
«
