1860. aastateks võimaldasid kujunev rahvuslik iseteadvus ja soodne majanduslik ning poliitiline olukord ehitusega pihta hakata. Krundi ja ehituskivid annetas kaupmees ja Toomgildi vanem Hans Heinrich Falck.
Uus Kaarli kirik pühitseti sisse 1870. aastal, kuigi ehitust alustati juba kaheksa aastat varem. Venimine oli seotud rahapuudusega.
Kiriku projekteeris baltisaksa arhitekt Otto Pius Hippius (1826–1883). Kiriku projekt valmis juba 1858. aastal, kuid nurgakivi pandi alles 1862. aastal. Kiriku lõplikku valmimist autor ise ei näinudki. Katus jõuti peale 1870. aastaks, mil kirik ka sisse õnnistati. Tornid lõpetati alles 1882. aastal, kuid siseviimistlus ning altarimaalid võtsid veel aega. Kirik ei ole praegugi täielikult lõpetatud: puudu on näiteks projektis ettenähtud raidkujud seinaniššides.
Kirikuhoone on uusromaani stiilis. Voldemar Vaga leiab, et "välisarhitektuuri iseloomustavad omavoliliselt käsitletud romaani stiili vormid." Karin Hallase sõnul on aga Kaarli kiriku puhul tegemist stiili sügava teadvustamise ja põhimõttelise käsitlusega.
Kaarli kiriku suursugune ja avar interjöör tuleb esile tänu selle erilisele katusekonstruktsioonile, mis võimaldas luua ühtse, piilaritega liigendamata ruumi. Selle projekteeris Otto Pius Hippius koos tuntud konstruktori Rudolf von Bernhardiga. Bernhardi projekteeritud puust laekonstruktsiooni peeti omal ajal ehitustehnika suursaavutuseks, mille mudel jäi ehtima Eestimaa provintsiaalmuuseumi ja Peterburi Tsiviilinseneride Instituudi ekspositsiooni. Bernhard oli omal ajal niivõrd mainekas insener, et kui 19. sajandil tekkisid Rooma Peetri kirikusse praod, kutsuti ka tema Peterburist Rooma probleemiga tegelema.