Till en början fanns det bara en begravningsplats här, Brunkebergskyrkogården, och inte någon kyrka. Hur gammal begravningsplatsen verkligen är vet man inte med säkerhet. Enligt en del källor skulle platsen ha använts som kyrkogård ända sedan slutet av 1200-talet, då Magnus Ladulås anlade S Örjans hospital på nedre Norrmalm.
När Jacobs församling grundades 1643 fanns det inte plats för någon begravningsplats runt kyrkan, och då blev Brunkebergskyrkogården församlingens begravningsplats.
Så småningom byggdes ett begravningskapell vid kyrkogården,
S:t Johannes kapell, som stod färdigt 1651.
Kapellet var en enkel, korsformad, tjärad kyrka som var avsedd för begravningar men fick så småningom status som kapell inom Jacob-Johannes församling.
Kapellet var troligen ett provisorium, eftersom man redan på 1670-talet diskuterade att uppföra en stenkyrka. Den diskussionen drog ut på tiden och först på 1750-talet författades ett memorial om en ny kyrka men något beslut fattades inte.
Först på 1770-talet inhämtade församlingen Gustav III:s tillstånd att bygga en stenkyrka. Uppdraget gick till Jean Eric Rehn, som gjorde flera förslag till S:t Johannes kyrka. De första ritningarna blev inte godkända och Jean Eric Rehn fick omarbeta dem. Den kyrka som slutligen började byggas den 14 september 1783 hade vissa klassicistiska inslag.
Kyrkbyggandet startades med stor energi; stenhuggare kontrakterades, schaktningsarbetet påbörjades, en trämodell av kyrkan tillverkades. Men då kom ett brev från Gustav III, som strax efter det att grundstenen lagts, rest till Italien. Brevet var avsänt från Rom den 24 januari 1784: allt arbete på kyrkan ska stoppas. Gustav III hade under sin resa kommit i kontakt med den nyantika strömningen på kontinenten och ansåg att Jean Eric Rehns kyrka var gammalmodig.
I Rom hade Gustav III träffat den franske arkitekten Léon Dufourny, som nu fick i uppdrag att göra nya ritningar till S:t Johannes kyrka.
Hans förslag var avsevärt mycket större och dyrare än Rehns. Förslaget visade en kyrka i extrem nyantik stil: den var en korskyrka utan fönster, med absider i öst och väst och med den tung dorisk tempelgavel framför huvudentrén. Kyrkan skulle byggas med grovhuggna kvaderstenar. Denna nyantika byggnad, utan anknytning i svensk kyrkotradition, kändes säkerligen mycket främmande för Johannes kyrkogård och planerna på en stenkyrka sköts på framtiden. I stället reparerades träkyrkan och byggdes ut.
Mot slutet av 1800-talet aktualiserades planerna på en ny kyrka och en tävling utlystes. Carl Möllers nygotiska förslag valdes och den 14 september 1883 – på hundraårsdagen av den förra grundläggningen – stadfästes förslaget och på pingstdagen 1890, den 25 maj, invigdes den nya kyrkan. Kung Oscar II var närvarade och ärkebiskop Anton Niklas Sundberg förrättade invigningen.