Vor der heutigen Kirche "Unserer lieben Frau" hatte Fischerhude bereits eine Kapelle, die ebenfalls der Jungfrau Maria geweiht war. Sie befand sich an der selben Stelle wie das heutige Kirchengebäude. Die Fischerhuder Kirche war "Filial" der Wilstedter Kirche.

Man nimmt an, dass sie in den letzten Jahren des 13. Jahrhunderts errichtet wurde. Zu diesem Schluss kommt man aufgrund einer Notiz, die sich im Besitz des Hauptlehrers Heinbokel fand:

Bei der Reperatur des Altares im Jahre 1841 fand man einen Pergamentstreifen mit der Inschrift, "dass der Altar 129- (letzte Ziffer fehlt) von Kölner Mönchen gegründet sei. Nachforschungen in Köln haben dies bestätigt."

Eine andere Quelle sieht als Zeitpunkt der Kapellengründung das Jahr 1494. Sie stüzt sich auf alte Akten aus dem Pfarrarchiv. Dort heisst es: "Hoc altare est aedificatum in honore b. mariae virginis A. D. MCCCCLXXXXIV." Für die Glaubwürdigkeit dieser Quelle sprechen sechs Heiligenfiguren, die nach Ansicht von Kunsthistorikern jedenfalls teilweise aus dem 14. Jahrhundert stammen.

Außer einem Kaufbrief sind keine Urkunden aus der Zeit vor der Reformation vorhanden. Wann diese eingeführt wurde, ist so nicht belegbar. Aufgrund der Abhängigkeit von der Wilstedter Kirche ist jedoch anzunehmen, dass die Reformation an beiden Orten im Jahre 1567 durchgeführt wurde.

Als Schweden im Jahre 1648 die Herzogtümer Bremen und Verden übernahm, wurde auch die kirchliche Verwaltung neu geordnet: Wilstedt und Fischerhude wurden der Präpositur Zeven Ottersberg zugeordnet.

Später im 17. Jahrhundert soll Fischerhude sogar zu Arbergen gehört haben. Heute wird jedoch davon ausgegangen, dass es sich dabei lediglich um einige Höfe außerhalb des Ortes handelte, die bei Überflutungen besser über Sagehorn nach Arbergen kommen konnten.

Die alte Kapelle war im Laufe der Jahre so baufällig geworden, dass man sich im Jahre 1841 zu einem Erweiterungsbau durchringen musste. Dieses Jahr wird somit als Baujahr für die heutige Kirche angenommen, auch wenn es später noch bauliche Veränderungen gab. Dazu zählt besonders der Umbau nach der Trennung von Wilstedt.