Die erste urkundliche Erwähnung stammt aus dem Jahre 950. In dieser Urkunde heißt es, dass König Otto I. (912 bis 973) dem Vasallen seines Sohnes Ludolf, dem Grafen Gerung, sechs “Hufen” Land (etwa 180 Morgen) in den Gemarkungen Wallau, Breckenheim und Nordenstadt schenkte.
Nordenstadt ist in Wirklichkeit jedoch viel älter. Es bestand schon zur Siedlungszeit der Franken als Dorfschaft. Das wohl älteste Relikt der Nordenstadter Vergangenheit ist ein fränkisches Gräberfeld, das am Ortsausgang des Dorfes, am heutigen Grabenweg, gefunden wurde. Archäologen stellten fest, dass die Gräber aus dem 6. Jahrhundert stammen. Es ist durchaus möglich, dass Nordenstadt, wie der Nachbarort Wallau, als kleine Siedlung bereits seit der Keltenzeit bestand und somit mehr als 2000 Jahre alt ist.
Nordenstadt befand sich im Jahre 950 auf einem gesegneten Stück Erde, das sich die fränkischen Könige als besonderen Besitz vorbehalten hatten. Es hieß nach der fränkischen Gauverfassung der “Königssundergau”.
Der Gau war gleichzeitig auch Grafschaft, also eine zusammenhängende Verwaltungseinheit. Den Mittelpunkt des Gaues bildete Mechthildshausen, wo sich auch das Grafengericht befand. Im Laufe der Zeit wechselte der Name der Gemeinde öfters.

Aus “Norminstatt” wurden “Nordinstatt” und “Norstat”, später “Norderstadt” und ab 1145 “Nordenstadt”. Der Name selbst weist auf den fränkischen Ursprung der Bewohner hin. Frei übersetzen lässt sich Nordenstadt vermutlich mit “die Wohnstätte des Nornin oder Norin”.