Da bebyggelsen langs Holmbladsgade, og sidegaderne kom til i årene omkring 1900, hørte det nye kvarter til Nathanaels Kirkes sogn.
Men i 1924 blev området fra Badensgade og ud til Øresundskysten udskilt som et selvstændigt sogn, der fik sin egen kirke, Allehelgens Kirke.
Kirken blev opført fra 1924, og blev tegnet af arkitekten Thomas Havning (1891-1976). Han fik 1. præmie i en udskrevet konkurrence om tegninger til kirken.
I starten bestod kirken blot af krypten, som primært lå under jordoverfladen. Ydermurerne over jorden var derfor i de første år kun få meter høje og avisen “Social-Demokraten” skrev, at kirken var smagløs og skamskændede kvarteret.
I 1932 var den egentlige kirke færdig og havde nu hele 550 siddepladser. Samtidig blev der opført en præstebolig i tilknytning til kirken.
Byggeriet blev finansieret af midler fra københavnske kirkefonde og indsamlinger forskellige steder i landet, bl.a. på Århusegnen.
Kirkeskibet er tilpasset til højden på karréerne langs Lergravsvej. Allehelgens Kirke har ikke noget tårn, men en tagrytter, hvor kirkens klokker er anbragt.
På grund af den høje krypt, der bruges som mødesal, er indgangen til det egentlige kirkerum ad en høj trappe i vestgavlen mod Ungarnsgade.
Over indgangsdøren sidder et citat fra Johannes Åbenbaring i Bibelen: “Herre, du alene er hellig, og alle folkene skal komme og tilbede for dit ansigt”.
