Aufgrund der Verkehrslage nicht verwunderlich, dass in der Gegend des heutigen Altendorf bereits vor Christi Geburt eine große Siedlung der Kelten existierte. Diese Siedlung gehört zu den größten bisher entdeckten keltischen Talsiedlungen in Nordbayern.

Im Jahre 1013 wird Seußling zum ersten Male urkundlich erwähnt, als König Heinrich, der spätere Kaiser Heinrich II, Großgerau bei Rüsselsheim gegen Seußling und Amlingstadt mit dem Bischof von Würzburg tauscht.

Bedeutend für den Ort Altendorf war das Jahr 1347, in dem Konrad von Schlüsselberg auf seiner Burg Neideck im Kampf gegen die Truppen die Bischöfe von Würzburg und Bamberg, sowie die Burggrafen von Nürnberg unterlag und ums Leben kam.

Aufgrund der günstigen geographischen Lage wurde die Postroute von Nürnberg nach Hamburg, die 1663 eingerichtet wurde, von der Thurn- und Taxisschen Posthalterei durch das Regnitztal festgelegt, während die älteren Straßen eher auf den Höhen liefen.

Mit dem Reichsdeputationshauptschluss des Jahres 1802 kamen Altendorf und Seußling wie viele andere Orte auch zum Kurfürstentum Bayern, das 1806 zum Königreich erhoben wurde.