Nachdem die Horner Gemeinde rund um die Martinskirche in den 1950er Jahren ständig anwuchs, beschloss der Kirchenvorstand, Töchtergemeinden zu gründen. Nach Philippus (1957) und Nathanael (1958) wurde die Kapernaum-Kirche im Dezember 1961 eingeweiht. Erbaut wurde die Kirche nach Plänen von Otto Kindt. Zum Areal der Kirche gehörte auch ein Gemeindehaus, zwei Pastorate und ein Kindergarten.
In den 1960er Jahren sorgte besonders die Jugendarbeit von Pastor Weißbach weit über die Hamburger Grenzen hinaus für Aufsehen. So schaffte es der erste Beatgottesdienst mit einer Band neben dem Altar sogar in die Tagesschau.
Im Jahre 2000 wurde anhand eines Baugutachtens festgestellt, dass die Kirche sanierungsbedürftig war und die Gemeinde dazu 1,8 Mio Euro hätte aufbringen müssen. Man trennte sich daraufhin von der Kirche und den übrigen Gebäuden und verkaufte sie an einen Investor. Die Orgel ging an die Christuskirche in Hamburg-Hamm und die Glocken an die Ansgar-Kirche an der Langenhorner Chaussee.
Im Bereich des 2008 abgerissenen Gemeindehauses entstand ein Pflegeheim, auf dem Areal von Pastorat und Kindergarten eine Altenwohnanlage. Für die Kirche waren mehrere Projekte geplant, die aber an Kosten und Bausubstanz scheiterten. 2013 konnte mit der Al Nour-Gemeinde ein Vertrag geschlossen werden, der die Umwandlung in eine Moschee vorsieht.
Otto Kindt (1909 - 2006) war ein deutscher Architekt. Neben Kirchenbauten schuf er zwischen 1965 und 1970 die drei charakteristischen Röhrenbahnhöfe Hauptbahnhof-Nord, Gänsemarkt und Messehallen.