The orbital structure of the asteroid belt holds a record of the Solar System's dynamical history. The current belt only contains ${\rm \sim 10^{-3}}$ Earth masses yet the asteroids' orbits are dynamically excited, with a large spread in eccentricity and inclination. In the context of models of terrestrial planet formation, the belt may have been excited by Jupiter's orbital migration. The terrestrial planets can also be reproduced without invoking a migrating Jupiter; however, as it requires a severe mass deficit beyond Earth's orbit, this model systematically under-excites the asteroid belt. Here we show that the orbits of the asteroids may have been excited to their current state if Jupiter and Saturn's early orbits were chaotic. Stochastic variations in the gas giants' orbits cause resonances to continually jump across the main belt and excite the asteroids' orbits on a timescale of tens of millions of years. While hydrodynamical simulations show that the gas giants were likely in mean motion resonance at the end of the gaseous disk phase, small perturbations could have driven them into a chaotic but stable state. The gas giants' current orbits were achieved later, during an instability in the outer Solar System. Although it is well known that the present-day Solar System exhibits chaotic behavior, our results suggest that the early Solar System may also have been chaotic.Read less <