Esimesed teated Tõnismäel asuvast kabelist pärinevad XIV sajandist. Kabel oli pühendatud pühak Antoniusele. Võib oletada, et kabel ja selle ümber kujunenud kalmistu olid määratud Toompea kogukonna mittesakslasest elanikkonna tarbeks.

Toompea Kaarli Kogudus võib ajalooliselt tagasi vaadata XVII sajandisse. 1670. aastal laskis Rootsi kuningas Karl XI Tõnismäele ehitada kreeka risti kujulise puukiriku, mis oli mõeldud nii eestlastele kui soomlastele. Kirik õnnistati 4. advendil 1670 ning nimetati Rootsi kuninga auks Kaarli kirikuks. Kaarli puukirikule kinkis Karl XI 1696. aastal kaks tornikella Vene vägede pealetungi eel 1710. aasta augustis põletati kogu linna kindlustuse ees asunud Tõnismäe hoonestus, sealhulgas ka Kaarli kirik. Pühakoja hävimine viis mõne aastakümnega suikvele kogudusegi - osa rahvast liitus Pühavaimu, osa Jõelähtme ning Keila kogudustega.

Taas hakati hingusele läinud Kaarli kogudust ja kirikut meenutama 19. sajandi keskel, mil kasvas vajadus ehitada suurem pühakoda eesti koguduse tarbeks. Raha kogumist uue kiriku jaoks alustati 1850. aastate lõpupoole.

18. okt. 1862 pandigi nurgakivi Tallinna ühele suurimale pühakojale - Kaarli kirikule. Projekti autoriks oli Eestiga tihedalt seotud Peterburi arhitekt Otto Pius Hippius. Samal ajal taastati ka kogudus, kes esimestel aastatel kasutas ajutist abikirikut, mis uue kiriku valmides muutes tarbetuks ja lammutati.

20. dets. 1870, täpselt 200 aastat pärast esimese kiriku õnnistamist, peeti uues kirikus I jumalateenistus. Selleks ajaks ei olnud kirik veel lõplikult valmis, puudusid altarimaal ja tornid. Siiani on puudu projektis ettenähtud figuurid seinanissides. 1870 aastal pakuti välja kaks võimalikku varianti. Esimese neliku moodustasid mehed, kellest kolm oli tihedalt Peterburiga seotud: kiriku ehitust on rahaliselt toetanud doktor Philipp Karell, kes oli üks esimesi eesti soost arste ning aastatel 1849-1879 ka vene keisri ihuarstiks; Peterburi professorid Rudolf von Bernhardt ning Otto Pius Hippius, kellest esimene oli katuskonstruktsiooni autor ja teine kiriku arhitekt ning krundi ja ehituskivid annetanud Toompea Gildi vanem Hans Heinrich Falck. Teise nelikusse kuulusid rootsi kuningas Gustav II Adolf (valitses 1611-1632); Martin Luther; vene keiser Aleksander II (valitses1855-1881), kes 1864.a. kinkis kogudusele Komandandi maja koos suure viljapuuaia ja linnatorniga Kiek in de Kök ja üks Eesti usutegelane. 1994. aastal valmistas eesti skulptor Tauno Kangro 4 evangelisti eskiisid, kuid needki jäid paigaldamata.

19. sajandi Eesti sakraalehitistest on Kaarli kirik suurejoonelisim - seda mitte üksnes mahutavuselt (1500 istekohta), vaid ka arhitektuurilt. Vormikõnelt historistlik, neoromaani suunitlusega tahutud paeplokkidest ehitis on põhiplaanilt ladina risti kujuline. Lääne-Euroopa katedraalidele sarnaselt on kiriku läänefassaad kujundatud kahe kõrge torniga. Peaukse kohal asub roosaken. Külgedelt kujundavad kirikut eelkõige kaaraknad, kuna kooriosa lõpetab polügonaalne apsiid, mida ümbritseb kabelipärga meenutav hooneplokk.

Kiriku arhitektuurne mõjukus keskendub interjööri - ruum tundub erakordselt avar ja suursugune. Eriliselt mängib kaasa võlvide eriline kandesüsteem, telliskaartele toetuv puitlagi, mis on võimaldanud suurt ruumi katta ilma ühegi vahetoeta (lahendus valmis koostöös arhitekt R. von Bernhardtiga). Põhiosa kiriku sisustusest - kantsel, pingistik, oreliväär jne - on teostatud O. P. Hippiuse jooniste järgi. Kiriku pindala on 1197,3 m², ruumala 33 889, 77 m³, sisekõrgus 20 m, tornide kõrgus ristipuuni 59,2 m.

Pühakoja väärtuslikumaks ehteks on kutsuvat Kristust kujutav freskotehnikas altarimaal “Tulge minu juurde kõik kes Te vaevatud ja koormatud olete, mina tahan teile hingamist saata” /Matt 11,28/, mis bütsantsi kirikute eeskujul on asetatud apsiidinissi. Selle eesti esimese fresko teostas Eesti soost kunstnik Johann Köler. Altarimaal valmis 10 päevaga 23. juuliks 1879 (Juuliuse kalendri järgi).

Kaarli kiriku vanemaks osaks on tornikellad. Põhjatornis asuv kell on kingitud 1696. a. Rootsi kuningas Karl XI poolt ning valatud Stockholmis. See on ka ainus mälestus Põhjasõja ajal hävinud esimesest Kaarli kogudusele kuulunud kirikust. Lõunatornis on 1870. a. kaupmees I. E. Steinbergi poolt annetatud Bochumis valmistatud malmkell.

1882 lõpetati F. Sableri projekti järgi tornide ehitus.

1884 valmis 30 registriga mehaanilise traktuuriga orel, mille ehitas Lääne-Virumaal sündinud esimene eesti soost orelimeister Gustav Norman. Orel asendati hiljem uuega.

1889 valmis Balti-Saksa kunstnikult Sally von Kügelgenilt lunastusmüsteeriumi kujutav kolmikmaal altari alaosas: “Jeesuse sündimine”, “Püha Õhtusöömaaeg”, “Jeesuse taganutmine”.

1909. a. paigutati kiriku peaukse kohal asuvasse roosaknasse ajanäitaja. Kell on ostetud Saksamaalt Weule tehasest.

1923 telliti maailmamainega firmalt E. F. Walcker & Co Ludwisburgis uus orel. Uus orel on registrite arvu poolest Eestis suurim. 3 manuaali ja pedaal, 81 registrit ja 3 transmissioniregistrit. Erakordselt võimas on Eestis ainuke pedaali 32’ keeleregister, mille madalaim heli asetseb kuuldavuse piiril (16 võnget sekundis).

Kaarli kogudus on liikmete arvult Eestis suurim.

Kõik kuupäevad enne 1. veebruarit 1918 on antud juuliuse kalendri järgi. Gregoriuse kalendri kuupäevade saamiseks tuleb XVIII saj kuupäevale lisada 11 ja XIX saj kuupäevale 12 päeva.