Da bebyggelsen langs Holmbladsgade, og sidegaderne kom til i årene omkring 1900, hørte det nye kvarter til Nathanaels Kirkes sogn.
Men fra 1924 udskiltes området fra Badensgade og ud til Øresundskysten 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. Byggeriet blev finansieret af midler fra københavnske kirkefonde og indsamlinger forskellige steder i landet, bl.a. på Århusegnen.
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.
