Kaarli kilsəsinin ilk taxta binası 1670-ci ildə, ehtimal olunur ki, təxminən 1570-1571-ci illərdə və ya 1577-ci ildə Livoniya müharibəsi zamanı dağıdılmış Müqəddəs Antoni kapellasının yerində tikilmişdir.

Kilsəyə Kaarli adı hakim monarxın İsveç kralı XI Karlın şərəfinə verilmişdir. Kilsə, Vışqorodda və şəhərətrafı ərazilərdə yaşayan və təxminən 1630-cu ildə estonlar və finlər üçün təşkil edilən kilsənin bir hissəsi idi. Kilsə tikilməzdən əvvəl yeni təşkil edilmiş kilsənin xidməti Vışqoroddakı binalardan birində köçürüldü.

Kilsənin ilk binası Şimal müharibəsi zamanı, 1710-cu ilin avqustunda rus qoşunları Tallinə yaxınlaşanda şəhərətrafındakı digər tikililərlə birlikdə yandırıldı. 1739-cu ildə kilsənin son keşişi Rakvereyə yaşamaq köçdü və kilsə nəhayət dağıldı.

XIX əsrin ortalarında Tallinin Müqəddəs Ruh kilsəsinin tutmu artıq, buraya ibadət üçün gələn estonlar üçün çox kiçik idi və yeni, daha geniş kilsə binasının inşasına ehtiyac duyulurdu. 1850-ci ildə yeni kilsənin tikintisi üçün pul vəsaiti toplanmağa başlandı. Ən böyük maliyyə yardım isə Estoniya cəngavərliyi tərəfindən edilib. Torpaq sahəsi və tikinti materiallarının bir hissəsi Dom gildiyasının ağsaqqalı Hans Falk (1791-1874) tərəfindən bağışlanmışdır. Memar Otto Qustav Gippius tərəfindən layihələndirilən tikinti 1862-ci ildə başlandı. Damının dizaynı isə R.B.Bernharda həvalə edilmişdi. İş memar R.Knüpfer tərəfindən həyata keçirilmişdir.

Kilsə qüllələrinin və son bəzək işlərinin ümumiyyətlə 1882-ci ildə tamamlanmasına baxmayaraq, məbəd 1872-ci ildə təqdis olundu. 1909-cu ildə əsas girişin üstündəki fasadda alman istehsalı olan saat tikildi. Kilsənin şəkli 1879-cu ilin iyulunda İohann Köler (ilk Estoniya freskası "Mənə gəl") tərəfindən çəkilmiş, qurbangahın aşağı hissəsinin üç hissədən ibarət kompozisiyasını 1889-cu ildə Salli fon Kügelgen çəkmişdir. Ən böyük çilçıraqlar Georg fon Meyendorf tərəfindən hədiyyə edilib. İlk kilsə orqan musiqi aləti Gustav Norman tərəfindən hazırlanmışdır, müasir olanı isə 1923-cü ildə Valker şirkəti tərəfindən hazırlanmışdır (81 registr, Estoniyada ən böyüyüdür). Kilsə zənglərinin ən qədimi 1696-cı ildə Stokholmda tökülüb.

Kilsənin Rahumaye qəbiristanlığında yeri var ki, buradakı ibadətgah 1911-1913-cü illərdə mühəndis Anton Vesson tərəfindən Kaarlovskaya kilsəsi ilə eyni üslubda tikilmişdir.