Biskupsstóllinn að skálholti var lagður niður og landið varð að einu biskupsdæmi 1798. Áður en það var 
talið nauðsynlegt að byggja dómkirkju í Reykjavík til að staðurinn gæti talizt sæma sem biskupsstóll (1801).
Árið 1788 var safnað saman því grjóti, sem talið var nauðsynlegt til byggingarinnar. Það var aðallega tekið úr túni Grjóta og flutt á sleðum á byggingarstað um veturinn. Hópur iðnaðarmanna kom frá Danmörku, en verkinu miðaði bæði seint og illa (1787-96), enda lágu kirkjusmiðirnir í drykkjuskap. Svo illa var gengið frá þaki kirkjunnar, að rífa þurfti það af 1792.
Engu að síður var kirkjan talin fullgerð árið 1796 og var vígð. Þá voru liðin 10 ár frá því, að Reykjavík fékk kaupstaðaréttindi og rúmaði kirkjan flesta íbúana. Kirkjan lak og slagaði svo mjög, að illvært var í henni. Í ljós kom, að mikið af viðnum, sem notaður var í kirkjuna, var fúinn frá upphafi. Árið 1815 var kirkjan dæmd hættuleg lífi og limum fólks og ónothæf til guðsþjónustu og tveimur árum síðar fór fram mikil viðgerð. Á hvítasunnudag 1825 við messu kváðu við miklir brestir í einum loftbita. Fólk ærðist af ótta og tróðst út hvar sem fært var.
Skírnarfonti Bertels Thorvaldsens var komið fyrir í kirkjunni árið 1839 og árið eftir eignaðist hún orgel. Kirkjan var endurbyggð og stækkuð á árunum 1847-1848 og sandurinn í múrverkið var fluttur hingað frá Danmörku. Teikningar að endurbyggingunni gerði L. A. Winstrup og danskir iðnaðarmenn voru fengnir til verksins. Kirkjan var að mestu viðhaldslaus næstu árin, þannig að ráðast þurfti að nýju í miklar endurbætur árið 1879 (Jakob Sveinsson, snikkari) og þá var kirkjunni komið í það horf, sem hún er í nú og tekur rúmlega 600 manns í sæti.
Þakið var upprunalega skífuklætt en núverandi koparþak var sett á kirkjuna um miðja 20. öldina. Kirkjan var friðuð 1973 og var gerð upp í áföngum árin 1977, 1985 og 1999 undir stjórn Þorsteins Gunnarssonar arkitekts.
Landsbókasafnið hafði aðsetur á lofti kirkjunnar þar til það var flutt í Alþingishúsið, sömuleiðis Forngripasafnið og síðar landsskjalasafnið.
Í Krukkuspá Jóns Guðmundssonar lærða frá 1650 stendur: Þegar níu prestar standa skrýddir fyrir altarinu í einu í Reykjavíkurkirkju og hinn tíundi biskup, þá sekkur hún.“ Kirkjan er í nýklassískum stíl. Síðustu endurbætur fóru fram árið 1999.
