Kirken er opkaldt efter den bibelske figur Johannes Døberen.
Ideen til kirken kom fra to præster, der mente at der skulle opføres en kirke ved Trekronergade i kvarteret syd for jernbanen. Der blev samlet penge ind, men de rakte kun til en lav bygning, den såkaldte kryptkirke, hvor der var en kirkesal.
Den blev tegnet af arkitekten Emil Engels, og stod færdig omkring 1930.
I begyndelsen var kirken en annekskirke under Jesuskirken, men fra 1941 blev Johannes Døbers Kirke centrum i sit eget sogn.
I 1950’erne var der blevet mulighed for at fuldføre byggeriet, så kirken stod endeligt færdig i 1958. Tårnet er tilføjet i 1991.