Im Dunkeln liegt die Gründung des Ortsteils Graben. Die durch die Gemarkung Graben von Süden nach Norden verlaufende, noch heute zum Teil sichtbare Römerstraße Kehl-Mühlburg-Heidelberg-Neuenheim, und die Funde römischer Münzen lassen darauf schließen, dass hier ein befestigtes Römerlager war. Zwischen dem 5. und 7. Jahrhundert wurde vermutlich das Haufendorf Graben gegründet.

1306 wurde Graben erstmals urkundlich erwähnt.

Im 14. und 15. Jahrhundert war Graben bereits Amtssitz, Marktflecken ("Graben der Markt") und Sitz eines Landkapitels (Dekanat). Der 30jährige Krieg brachte viel Not und Elend über Graben. 1622 hatte Graben 145 Bürger, 1648 waren nur noch 42 ansässig.

Im Orlean'schen Krieg, der 1688 ausbrach, zerstörten die Franzosen Schloss und Dorf Graben, so dass nur die Kirche, Rathaus und einige Gebäude übrig blieben. Die Bewohner des Dorfes lebten nun in den Wäldern und in den Nachbarorten. Ruhe, Ordnung und Aufschwung traten erst wieder in der Mitte des 18. Jahrhunderts ein.

Der Ort Neudorf entstand durch Zusammenwachsen zweier Rodungssiedlungen. Zum ersten Mal wird dieses "Neue Dorf" 1497 als Nuwdorff erwähnt.

Neudorf - darauf weist nicht nur diese späte Erstnennung, sondern auch die kleine Gemarkung, kleine Allmende und fehlender Gemeindewald hin - ist also der jüngste Ort der näheren Umgebung, zugleich aber auch einer der kleinsten und ärmsten.

Politisch gehörte Neudorf zum weltlichen Herrschaftsgebiet des Bistums Speyer, während Graben seit 1312 nicht mehr dazu gehörte, kirchlich dagegen war es Graben zugeordnet.

Die Zugehörigkeit der beiden kirchlich zusammengehörenden Orte zu zwei verschiedenen weltlichen Herrschaftsgebieten war für die weitere Entwicklung von nicht geringer Bedeutung. Im Jahre 1556 führte nämlich Markgraf Karl II. von Baden-Durlach in seinem Herrschaftsgebiet die Reformation ein, und somit mussten auch die Einwohner von Graben mehr oder weniger freiwillig zum Protestantismus übertreten, wogegen die Einwohner von Neudorf als weltliche Untertanen des Bischofs von Speyer am katholischen Glauben festzuhalten hatten.

Im 17. Jahrhundert soll der Ort Neudorf "einige Male in Schutt und Asche gelegt" worden sein und wurde außerdem wiederholt vom Hungertyphus und der Pest heimgesucht, so dass 1683 nur noch acht Familien Neudorf bewohnten.

An dem allgemeinen Aufschwung, den das rechtsrheinische Gebiet des Hochstifts Speyer in der ersten Hälfte des 18. Jahrhunderts erlebte, nahm auch Neudorf teil, was sich an dem relativ großen Bevölkerungszuwachs dieser Jahre ablesen lässt (1719/20: 48 Familien; 1742/43: 70 Familien).

Zusammen mit dem rechtsrheinischen Teil des Fürstbistums von Speyer fällt Neudorf am 1. Dezember 1802 dem Markgrafen Karl Friedrich von Baden zu. Ein besonderes Kennzeichen der ersten "badischen" Zeit ist die verhältnissmäßig starke Zunahme der Bevölkerung: zählte der Ort 1813 noch 537 Einwohner, so waren es 1852 bereits 1136 Einwohner. Aber die Einwohner, die von Feld-, Wiesenbau und Viehzucht lebten und deren Hauptnahrungsquelle der Torfstich war, blieben "mehr arm als reich", so dass in den 50er und 60er Jahren des 19. Jahrhunderts viele Familien ihr Glück in der Fremde suchten. Eine stetige Aufwärtsentwicklung setzte erst im letzten Viertel des Jahrhunderts ein.

Heute wohnen in Graben-Neudorf um die 11.000 Menschen.