Man nimmt an, dass die Gründer Nordsteimkes aus Flandern kamen. Es waren Spezialisten zur Urbarmachung von Sümpfen. Ein solches Sumpfgebiet war der Drömling im Verlauf der Aller. Also auch der weitere Bereich von Nordsteimke. Die Wanderung der Flamen werden wegen der vielen ähnlichen Namen angenommen: Steinbeck (NRW), Steimke bei Syke, Steimke bei Asendorf, Steinbeck bei Schneverdingen, Steinbeck bei Buchholz, Steimke bei Hankensbüttel, Steimke bei Brome, Klein Steimke, Nordsteimke, Steinbeck bei Ludwigslust, Steinbeck bei Bad Freienwalde.

Die Theorie der Wanderung wird durch eine Urkunde aus dem Jahr 860 untermauert, in der ein Ort „Stenbiki" (Steimke bei Asendorf) genannt wird.

Die Ortsgründung des Dorfes Nordsteimke kann um das Jahr 900 angenommen werden. Der Ort mag wendischen Ursprungs sein, gehörte dann aber zu Franken. Nachdem die Franken bereits um 500 zum Christentum übergegangen sind, wohnten in unserem Gebiet um das Jahr 1000 herum Christen, die sich ihre eigene Kirche bauen wollten. Hierzu nahmen sie Flamen zu Hilfe, die möglicherweise vorher zum Bauen von Burgen eingesetzt waren, - ehemalige Bewohner von „Steenbeque". Das ist eine holländische Schreibweise, die bis 1467 geführt wurde. Nach dem Bau der Kirche, deren Turm eine Schutzfunktion hatte, wurden sie im unmittelbaren Bereich der Kirche sesshaft. Sie übernahmen bis 1348 das Kirchenpatronat und gaben dem Ort ihren Namen „Stenbeke".

1238 wurde Nordsteimke dann erstmals urkundlich erwähnt.