I 1903 bad præsten ved Sankt Jakobs Kirke ved Østerbrogade, om at der måtte blive oprettet et nyt sogn på den del af Østervold, som var blevet bebygget i årtierne forud. Dermed dannedes Østervold Sogn som omfatter Stockholmsgade-kvarteret og Kartoffelrækkerne.
Det Københavnske Kirkefond stillede en grund til rådighed ved Upsalagade, og en komité indsamlede penge til opførelse af en kirke. Oprindeligt havde man ved udbygningen af Stockholmsgade-kvarteret udlagt Hjalmar Brantings Plads til placering af en kirke, men nu kom den altså til at ligge overfor Malmögade.
I første omgang blev der bygget en krypt-kirke – eller “grævlinge-kirke”, som den blev kaldt i folkemunde. Kirkerummet lå delvist under jorden, men havde alligevel plads til 450 kirkegængere.
Indsamlingen fortsatte, og i 1912 var der rejst tilstrækkelige midler til, at der kunne bygges en egentlig kirke. Kryptrummet blev derefter brugt som mødesal.
Man bad arkitekten Thorvald Jørgensen (1867-1946) om at tegne kirke. Han havde i årene forinden arbejdet med genopførelsen af Christiansborg Slot. Hans oprindelige tegning (herover) var dog ikke helt den kirke, der i sidste ende blev opført.
Kirken, der ved indvielsen fik navnet Esajas Kirke efter den bibelske profet Esajas, er et stort og monumentalt bygningsværk i romansk stil.
Kirken er korsformet, og har et stort, pyramideformet tårn samt to tårne ved indgangspartiet mod sydvest. De er formentlig inspireret af den sjællandske middelalderkirke i Tveje-Merløse.
Over indgangen står et citat fra Esajas Bog i Det Gamle Testamente.
Ved indgangen sidder to engle i granit, udført af billedhuggeren Anders Bundgaard.
Indvendig er kirken udsmykket med glasmosaikker af Joachim Skovgaard.
Nord for selve kirken ligger en præstebolig.
