Under Krimkrigen i 1850-årene og i tiden etter opplevde Tromsø by en stor økonomisk vekst, som også ga utslag i et sterkt økende folketall. Dette innebar at kirkekapasiteten var blitt altfor liten, og det be krevet oppføring av en ny, stor kirke.

Allerede i 1855-56 var det enighet om at en ny kirke skulle oppføres, og den gamle avhendes til Tromsøsunds menighet. I 1858 tegnet arkitekt Jacob Wilhelm Nordan et utkast til en korskirke. Planene var såvidt kontroversielle at man engasjerte arkitekt Christian Heinrich Grosch til å tegne en langkirke i tre, og Groschs andre utkast ble vedtatt i 1860. Kirken ble bygget i årene 1860-61, med Nils Olsen som ansvarshavende murmester og snekker Ditlev Gunnerus Evjen som byggmester. Kirken er oppført i laftet tømmer, og er panelkledt.

Kirken ble vigslet av biskop Carl Peter Essendrop 1. desember 1861, men først i 1862 var tårnet reist og utstyrt med klokker. Kirken fikk opprinnelig 984 sitteplasser og kostet omkring 10 000 spesiedaler å bygge. Innredningen var ikke fullført før midten av 1880-årene.

Kirken er en langkirke i tre, i en enkel nygotisk stil, med et høyt, avtrappet tårn. Store, forenklede nygotiske vinduer er jevnt fordelt utover langsidene - mellom pilastre - avbrutt av brede midtrisalitter med gavl.

Fra 1952 er kirken domkirke i Nord-Hålogaland bispedømme.