Bereits im Jahr 850 wurde am Scharmbecker Markt aus Holz die älteste Kirche der Gegend gebaut und erhielt den Namen des ersten Bremer Bischofs, des Heiligen Willehad. Von der 1150 neu errichteten Kirche aus Feldsteinen sind die Turmmauern bis heute erhalten. Das Kirchenschiff wurde 1745 durch ein wesentlich größeres Gebäude ersetzt, das bis heute erhalten ist. 1883 mussten die vier kleinen Ecktürmchen des Turmes von Maurermeister Johann Steeneck wegen Einsturzgefahr entfernt werden. Die kleine Glocke und die Uhrschlagglocke wurden 1915 für die Kriegsindustrie geopfert.
Eine 1678 von Arp Schnitger für 250 Reichsthaler gebaute Orgel wurde 1734 durch das noch heute gespielte und vom Schnitger-Schüler Erasmus Bielfeldt gebaute Instrument ersetzt, die sog. Erasmus Bielfeldt Orgel. Dem renommierten Orgelsachverständigen und Organisten Prof. Harald Vogel zur Folge ist „ein solches original erhaltenes Instrument … einzigartig“. Es sei das vollständigste und klanglich am besten erhaltene Werk aus der Schnitger-Schule und gehöre zu den wichtigsten historischen Orgeln Deutschlands. (Quelle: Hamme Report 28.1.2009)
Der Turm wurde 1870 nach Plänen des Hannoveraner Architekten Weyhe umgebaut und erhielt dabei den heutigen 8-eckigen Turmhelm. Quelle: R. Menkhoff: Chronik von Osterholz-Scharmbeck Band 1 Von Januar 2003 bis in das Jahr 2004 hinein war die Kirche für umfangreiche Renovierungsarbeiten geschlossen, dabei wurde u.a. eine neue Heizungsanlage eingebaut.
Die Kirchengemeinde St. Willehadi zählt heute ungefähr 11.000 Mitglieder in den Stadtteilen Scharmbeck, Buschhausen und Westerbeck sowie den Dörfern Hülseberg, Ohlenstedt und Garlstedt.