När på 1880-talet Caroli kyrka började bli för liten för stadens växande befolkning uppkom tanken att antingen ersätta kyrkan med en en ny och större eller att bygga ytterligare en kyrka på en annan plats i staden. Caroli kyrka fick mycket kritik under diskussionerna och ansågs arkitektoniskt bristfällig med den tidens uppfattning. Valet föll dock på det senare alternativet med en till kyrka. Under slutet av år 1896 tillsattes av kyrkostämman en kommitté med prosten Enander som ordförande som skulle utreda frågan och komma med detaljerade förslag. Till rådgivare anlitades Adrian C. Peterson. Han undersökte åtta olika platser för kyrkbygget innan en plats på landeriet Lugnets mark slutligen valdes. Stadsfullmäktige beslöt den 22 juni 1897 att här kostnadsfritt upplåta mark för den nya kyrkan.
Kyrkan är en kort enskeppig långhuskyrka med tvärskepp och rakslutet kor. Då den är bred relativt längden liknar den även en centralkyrka, tvärskeppsväggarna bildar nämligen med mittrummet en långsträckt åttakant. Exteriören knyter an till nygotiken bland annat genom tornet, tvärskeppet, koret, strävpelarna, de spetsbågiga fönsterna och portalen. Det finns emellertid andra delar i utformningen såsom trapphusen och byggnadsmaterialet på utsidan som återspeglar en modernare stil.
Sockeln består av granit medan resten av väggarna är av normalformatstegel. Tre band av granit delar av väggarna horisontellt. Av samma granit utgörs även fönstrens ramverk. Huvudportalens kolonner och arkivolter utgörs av gotlandssten. Takbeläggningen består av skiffer från Grythyttehed medan tornspetsen är täckt av koppar. Tornet har spetsbågiga valvöppningar till klockhuset, dess kolonner är av svart granit och kapitälen av brun belgisk sandsten. Tornet avslutas av gavlar i norr och söder varifrån tornspiran med fyra tureller börjar. Runt tornspetsen finns en krona och högst upp ett klot krönt med ett kors.
Huvudportalen är i en nisch som omges av spetsbågiga profilerade arkivolter och kolonner. Den avslutas uppåt med vimperg smyckad med krabbor och ringkors. Dörrarna är av mörkbonad ek och gotiskt smide. Ovanför dörrarna finns ett trepassformat fönster med ett rosfönster. Sidoportalerna, även dessa av mörkbonad ek, är svagt spetsbågiga medan ingångarna vid koret är rakslutna. Samtliga trappor vid dörrarna är av granit. Kyrkans fönster utgörs av fem låga fönster som är parvis ställda i norr och söder. Ovanför dessa befinner sig större spetsbågiga fönster. Ett runt åttapassfönster finns i väster. Koret hade innan ombyggnationen nio spetsbågiga fönster, tre var i norr, öst och söder. Katedralglas är insatt i fönstren.
Långhuset är uppdelat i ett brett kryssvälvt mittskepp i två travéer och sidoskepp i två våningar. De sistnämnda är täckta med tvärställda tunnvalv. Tornmuren är i väster genombruten av en bred valvbåge. Fyrkantiga pelare med knektar i hörnen bär upp valven. Kapitälen på kolonetterna har utförts efter tyska gipsmodeller. Alla bärande delar i kyrkan försågs med tegel från Bonn. Väggytorna putsades och fick ljusgul färg varpå dekorationer målades av Edvard August Bergh. Dekorationerna gjordes al secco med schablonmålade blad och blomlister samt fyllningar. Vidare målades i triumfbågen änglar, medaljonger med Kristus som världsdomare och evangelistsymbolerna. Stjärnvalvet som var rikt dekorerat innehöll texten: "Ära ske Gud, som från sin tron Till oss ser neder, Och Jesu Krist, hans ende Son, Som för oss alla beder".
I tornet byggdes vapenhus och vindfång, förrum finns även vid de andra ingångarna. Dessa har valv av tegel. Läktarna byggdes av trä och stöddes av järnbalkar samt tegelvalv. Med den första bänkinredningen fanns 1 230 sittplatser. Altarbordet fick en skiva i Carraramarmor och står på fyra kolonnetter av gul marmor från Ekeberg på en bas av vit fransk sandsten. Altaruppsatsen var snidad av ek i gotiserande stil och bestod av ett lågt retabel med ornament och förgyllda lister. I mitten fanns en korskrönt gotisk gavel och ett snidat ornament. Altarringen bildade en halvcirkel och var av brungul lackerad ek. Den första predikstolen var av brunbetsad ek och stod på en fot av fransk sandsten. Från början saknades tak vilket sedermera tillkom år 1930. Den gamla dopfunten i modifierade senromanska former var av ljusgul belgisk sandsten.
Kyrkobyggnaden efter ombyggnaden 1949–1952. Med tiden kom emellertid kyrkan att uppfattas betydligt som otidsenlig och omodern vilket ledde till att kyrkan under åren 1949 till 1952 genomgick en stor ombyggnad ledd av arkitekten Otar Hökerberg. Kontraktsprosten Emanuel Beskow och kyrkoadjunkten Torsten Ahlstrand var drivande i ombyggnationen. Förändringen av koret som ombyggnaden innebar medförde en ändring av kyrkorummet i sin helhet. De gamla sidoläktarna revs och nya byggdes längs tvärskeppets västväggar. Nere i kyrkan snedställdes bänkarna i tvärskeppet. Orgelfasaden byttes ut och nya takkronor tillkom. Läktarbarriären fick en ny utformning. Dörrarna till de gamla läktarna på ömse sidor av triumfbågen blev burspråk med nummertavlor. I koret togs dörrarna bort och ersattes med ett valv mot en bönekammare på norra sidan. En ny åttakantig sakristia byggdes norr om kyrkan av tegel med gul-gråputsade väggar och skiffertak. Kyrkan binds ihop med sakristian genom en gång. Fönstren i koret togs bort för att möjliggöra en stor muralmålning. Fönsterna från koret föreställande Petrus och Paulus flyttades till tvärskeppen.
Den nya predikstolen av ljus ek ritades av Hökerberg och försågs med reliefer av Torolf Engström. Relieferna föreställer kyrkoårets högtider med Advent, Jul- och trettondagstid, Passionstid, Påsk, Pingst, Trefaldighetstid och Domssöndagen. Till predikstolen hör ett ljudtak. En ny dopfunt av Liss Eriksson tillverkad av vit fransk sandsten tillkom vid ombyggnaden. Ett järnsmide av samme konstnär placerades i nischen vid funten. Även altaruppsatsen byttes ut till en ny av Christian Berg. Den är utförd i ofärgad polsk ek, har formen av en upptill rakt avslutad triptyk med reliefer föreställande evangelistsymbolerna. I nischen i korpus fanns ett gyllene krucifix som stals den 21 juni 2012 och ersattes av en replik av samme konstnär hösten 2013. Även altarringen förnyades under ombyggnationen.
Den centrala kormålningen, "Den stora måltiden", utfördes av Pär Siegård och Kaj Siesjö och stod klar den 19 februari 1952. Kristus står med utbredda armar ovanför altaret och flankeras av människor som kommer mot honom från alla håll samtidigt som vingårdsmannen och såningsmannen som symboliserar vin och bröd arbetar. Fresken på norra sidan skildrar liknelsen om den förlorade sonen medan den på den södra sidan föreställer den barmhärtige samariten.
Kyrkan återinvigdes av biskop Yngve Rudberg på Pingstdagen år 1952. Kyrkobyggnaden efter ombyggnaden 2005–2006. Den senaste stora ombyggnaden ägde rum under år 2005 och 2006. Innan dess hade Petruskapellet i det norra tvärskeppet blivit färdigt år 1981. Den 11 månader långa renoveringen inbegrep bland annat ett nytt vindfång vid ingången, rengöring, nya ljud- och bildsystem med två storbildsskärmar, Petruskapellet anpassades för dop och vigsel samt vissa nya textilier. Återinvigningen ägde rum den 21 maj 2006 med biskop Erik Aurelius.
Den första orgeln placerades bakom den västra läktaren i ett välvt tornrum som öppnade sig mot kyrkorummet. Åkerman & Lund Orgelbyggeri i Stockholm tillverkade orgeln som hade 25 stämmor fördelade på två manualer och pedal. Bälgarna drevs med elektrisk motor. Fasaden var pseudogotisk i ljusgul lackerad ek. Den andra orgeln som kom i samband med ombyggnationen 1949–1952 då den tidigare orgeln om- och tillbyggdes omfattande av A. Magnusson Orgelbyggeri AB i Göteborg. Stämantalet blev efter ombyggnationen 52, fördelade på fyra manualer och pedal. Fasaden uppdelades i två partier som delades av med en spetsbåge, vilken kröntes av en skulptur föreställande Sankta Cecilia. Vidare smyckades orgeln av en basunblåsande ängel.
Efter ett flertal besiktningar av den gamla orgeln år 1970 ansågs den så dålig att en renovering inte var möjlig vilket ledde till att en ny orgel beställdes av den danska firman Marcussen & Søn år 1972. Orgeln byggdes mellan 1975 och 1976 och invigdes Bönsöndagen 1976 under medverkan av biskop Helge Brattgård. Den så kallade Marcussen-orgeln har 3 840 pipor, den största tennpipan väger 52 kg och är 5 meter lång.

Tillbaka till Gustav Adolfskyrkan