W 1664, za rządów regenta króla Karola XI, podjęto decyzję o zbudowaniu nowej świątyni. Zadanie to zlecono architektowi miejskiemu, Jeanowi de la Vallée. Kamień węgielny pod budowę nowego kościoła położono w 1669; plany świątyni znalazły się w dziele Erika Dahlbergha Suecia Antiqua et Hodierna. Budowę jednak musiano wkrótce przerwać z powodu braku środków finansowych. Udało się jednak wznieść prowizoryczny, drewniany kościołek w okolicach skrzyżowania ulic Storgatan i Artillerigatan. Tam też rozpoczęto w 1725 roku budowę nowego, murowanego kościoła, tym razem według projektu architekta Görana Josuæ Adelcrantza. Po dwunastu latach, 21 sierpnia 1737 konsekrowano gotowy kościół.
Architektura Zewnętrzna bryła kościoła thumb|Storklockan (Duży dzwon) Dzisiejszy budynek kościoła Jadwigi Eleonory odzwierciedla dwa odrębne etapy jego powstawania. Budynek kościoła jest wzniesiony ma planie rotundy, typowym dla kościołów skandynawskich. Kopuła natomiast różni się zasadniczo od części dolnej, tak co do stylu, jak i rozmiarów. Powstała ona później, w latach 1866–1868, według projektu architekta Fredrika Wilhelma Scholandera (1816–1881) przy okazji prac remontowych prowadzonych przez nadwornego architekta Bror Carla Malmberga (1818–1877).