Kirken har navn efter den israelske by Nazareth, hvor Jesus efter Bibelens fortælling voksede op.
Med udbygningen af Nørrebro og Østerbro i slutningen af 1800-tallet, voksede befolkningstallet voldsomt. De to bydeles første kirke, Sankt Johannes Kirke, blev derfor hurtigt utilstrækkelig, og der blev i årene omkring 1900 opført flere nye. Alene i Nazareth Kirkes distrikt, boede dengang 14.000 indbyggere.
I kvarteret omkring Ryesgade holdt en ung kateket gudstjenester i opgangene og under træerne i haven til Ryesgade 105. Der blev dannet et menighedssamfund, der havde til opgave at få oprettet en kirke i den tæt befolkede Ryesgade. Det lykkedes i 1892.
Kirken var dog i begyndelsen en midlertidig bygning, opført af blikplader som blev leveret af et firma i England (billedet herover).
Denne kirke var vanskelig at varme op, og ydermere smed børnene sten på pladerne under søndagsgudstjenesten.
Den midlertidige kirke var betalt af midler fra Det Københavnske Kirkefond, som støttede etableringen af kirker i Københavns nye kvarterer.
Takket være en lokal indsamling, blev det muligt i årene op til 1904 at opføre en egentlig kirke. Den midlertidige blik-kirke blev flyttet til Sjællandsgade på Nørrebro, hvor den fungerede indtil åbningen af Simeons Kirke.
Den permanente kirke i Ryesgade var tegnet af arkitekt Victor Nyebølle (1862-1933) som hans første arbejde i København.
Han lod sig inspirere af de romanske kirker i Norditalien og indpassede kirken i husrækken i gaden, så facaden mod Ryesgade er ganske smal, mens kirkeskib og -kor strækker sig langt bagud på grunden. Det slanke og næsten 50 meter høje tårn, viser kvarterets beboere, hvor kirken ligger.
Kirken er bygget i røde mursten, men hviler på et fundament af granit. På facaden er et relief med bibelske motiver (billedet herunder), udført af billedhuggeren Thomas Bærentzen (1869-1936).
I 1905 blev Nazareth Kirkes sogn delt, da Fredens Kirke i Ryesgade åbnede. I dag fungerer de to kirker som samlingssteder i et fælles sogn.