Tre kvinder havde i 1886 stiftet Foreningen til opførelse af små kirker i København, som arbejdede for at afhjælpe manglen på kirker i den hastigt voksende by.
De overtog en kirkebygning fra en frimenighed i baggården til Blågårdsgade 40 (billedet herover) og indrettede den til folkekirke for kvarteret. I folkemunde blev den kaldt “De unge pigers kirke”.
Bygningen var oprindeligt tegnet af arkitekten Robert Møller.
“Baggårdskirken” blev fra 1889 en filialkirke til Sankt Johannes Kirke og senere til Hellig Kors Kirke. I 1917 blev Bethlehemskirkens sogn selvstændigt.
I 1938 kunne sognet indvie en ny kirkebygning, der ikke længere lå i baggård, men med facade til den nye, gennemgående vej Åboulevard.
Tegningerne til den nuværende kirke blev påbegyndt at arkitekten Peder Vilhelm Jensen Klint (1853-1930), men han blev ikke færdig med projektet før han døde. Derfor blev kirkens endelige udseende udformet af hans søn, Kaare Klint (1888-1954), der også har tegnet det meste af inventaret.
P. V. Jensen Klint nåede dog at tegne menighedshuset, der ligger i Tømrergade.
Kirken har mange lighedstræk med P. V. Jensen Klints store byggeri Grundtvigs Kirke.
For at skærme for trafikstøjen fra vejen, fik kirken et særligt, lydisoleret indgangsrum i stedet for et tradtionelt våbenhus.
Indgangsrummet og baldakinen (ciboriet) over alteret er inspireret af Fødselskirken i Bethlehem.
Bethlehemskirken er i dag ikke længere en folkekirke, men drives af et menighedssamfund.
