Gustav Adolfs kyrka byggdes i början av 1900-talet, vid en tidpunkt då befolkningen i Borås ökade snabbt. Det fanns dock bara en kyrka i staden, Caroli kyrka, och den bedömdes vara för liten. Man utlyste en tävling, där 16 bidrag och kom in, och det vinnande förslaget stod arkitekten Carl Bern för. Han var specialutbildad till kyrkoarkitekt, och framför allt verksam i Tyskland.
Byggnadsarbetet inleddes 1903, och tre år senare stod kyrkan klar. Den uppfördes i nygotisk stil, men den har även element i mer modern stil. På Kristi himmelfärdsdag 1906 invigdes kyrkan av biskop Hjalmar Danell.
1939 delades Borås stadsförsamling i två: Borås Caroli och Borås Gustav Adolf. Gustav Adolfs kyrka blev då församlingskyrka i Gustav Adolfs församling. Idag omfattar denna församling även Dammsvedjans och Hässleholmens kyrka.
I början av 50-talet renoverades kyrkan grundligt under ledning av Otar Hökerberg, och en nyinvigning hölls 1952. Det var genom denna renovering och tillbyggnad som kyrkan fick sitt nuvarande utseende.
De gamla sidoläktarna revs och nya byggdes längs tvärskeppets västväggar.
Bänkarna i tvärskeppet placerades snedställt.
Orgelfasaden byttes ut.
Nya takkronor sattes upp.
Läktarbarriären fick en ny utformning.
Dörrarna till de gamla läktarna på var sin sida av triumfbågen ersattes av burspråk med nummertavlor.
Dörrarna till koret togs bort. De ersattes med ett valv mot en bönekammare på norra sidan.
Kyrkan fick en fristående sexkantig sakristia, som anslöts till kyrkobyggnaden genom en meditationsgång.
Fönstren i koret togs bort för att möjliggöra en stor muralmålning. Två av dessa, som föreställer Petrus och Paulus, flyttades till kyrkans tvärskepp. En ny kormålning, “Den stora måltiden”, utförd av Pär Siegård och Kaj Siesjö, färdigställdes 19 feburari 1952.
Kyrkan fick en ny predikstol i ljus ek, med reliefer som visar kyrkoårets högtider: advent, jul, passionstid, påsk, pingst, trefaldighetstid och domssöndagen.
Kyrkan fick en ny dopfunt, i vit fransk sandsten, designad av Liss Eriksson.
Ytterligare en renovering gjordes 2006, där kyrkan bl.a. fick nya ljud- och bildsystem.