Are there bands of orbital stability between the terrestial planets in which planetesimals could have survived since the origin of the Solar System? Previous work has demonstrated orbital stability for 100 Myr of initially near-circular and coplanar small bodies in a region termed the “Earth-Mars belt“ from 1.08 au < a& lt; 1.28 au. Via numerical integration of 3000 particles, we studied orbits from 1.04-1.30 au for the age of the Solar system. We show that on this time scale, except for a few locations where mean-motion resonances with Earth affect stability, only a narrower “Earth-Mars belt” covering a∼(1.09,1.17) au, e<0.04, and I<1 degree has over half of the initial orbits survive for 4.5 Gyr. In addition to mean-motion resonances, we are able to see how the nu3, nu4, and nu6 secular resonances contribute to long-term instability in the outer (1.17-1.30 au) region on Gyr time scales. We show that all of the (rather small) near-Earth objects (NEOs) in or close to the Earth-Mars belt appear to be consistent with recently arrived transient objects by comparing to a NEO steady-state model. Given the <200m scale of these NEOs, we estimated the Yarkovsky effect drift rates in semimajor axis, and use these to estimate that a diameter of ∼100km or larger would allow primordial asteroids in the Earth-Mars belt to likely survive. We conclude that only a few 100 km scale asteroids could have been present in the belt’s region at the end of the terrestrial planet formation.