Der Heidengraben ist mit einer Gesamtfläche von 1.662 Hektar nicht nur das größte keltische Oppidum in Deutschland, sondern auch eines der größten in Europa. Der Begriff „Oppidum“ für stadtähnliche, befestigte Großsiedlungen der späten Kelten des 2. und 1. Jh. v.Chr. in Mitteleuropa wurde in Anlehnung an Caesars Beschreibung solcher Anlagen der Kelten in Gallien übernommen. Im Gegensatz zum heutigen Frankreich ist im Heidengraben allerdings keine Begegnung zwischen Kelten und Römern nachgewiesen. Funde aus der Römerzeit aus dieser Gegend sind rund 200 Jahre jünger.
Namensgebend für die Gemeinde Grabenstetten war wohl der Verteidigungsgraben des Oppidums, auffälliger in der Landschaft ist jedoch der erhabene Wall, den man heute noch über weite Strecken verfolgen kann. Der Verlauf der Befestigungsanlage um den Heidengraben wurde der halbinselartigen Form der Hochfläche angepasst, deren steile Abhänge einen natürlichen Schutz boten. An der schmalsten Stelle südlich von Grabenstetten schnürt der Wall die Hochebene von der Albhochfläche ab. Dort sowie an Stellen, wo Wege aus den tief eingeschnittenen Tälern emporführen, wurden Tordurchlässe angelegt, meistens in Form von sogenannten Zangentoren, wo der eindringende Gegner in einer langgezogenen Torgasse sprichwörtlich „in die Zange“ genommen werden konnte. Diese Tore sind heute alphabetisch numeriert und werden als Tor A bis Tor H bezeichnet. Der Wall war ehemals deutlich höher als heute und als sogenannte Pfostenschlitzmauer aus Holzpfosten, Steinen und Erde errichtet. Am Tor G in der Gemeinde Erkenbrechtsweiler wurde nach Ausgrabungen durch das Landesdenkmalamt Baden-Württemberg ein Stück dieser Mauer rekonstruiert.