Kirken blev bygget i midten af 1890’erne. Oprindeligt kaldte man den blot Kirken på Utterslev Mark, men da den i begyndelsen var en del af Sankt Stefans Kirkes sogn, opkaldte man den efter en landsby ved Genesareth Sø, der kendes fra Bibelen.
Den oprindelige plan var, at bygge kirken længere mod øst ved Ørnevej , men her havde ligget en losseplads for latrin, så det var ikke muligt at bygge her.
Arkitekten var Valdemar Koch (1852-1902), der senere tegnede en række andre kirke i Københavnsområdet.
Byggeriet blev især finansieret af støtte fra Den Københavnske Kirkefond, men også gennem gaver, fra bl.a. firmaet Jacob Holm & Sønner, som havde en fabrik ved Lygten.
Oprindeligt lå kirken helt frit, men er siden blevet omgivet af etagejendomme.
I 1916 blev der opført to menighedslokaler i tilknytning til kirken, og i 1923 tegnede arkitekt Julius Berg en præstebolig på Svanevej 9.
I 1933 blev Kapernaums Kirkes sogn delt, da Ansgar Kirke blev opført ved Mågevej. Senere er også >Tagensbo kirkes sogn blevet udskilt.