The asteroid belt is an open window on the history of the Solar System, as it preserves records of both its formation process and its secular evolution. The progenitors of the present-day asteroids formed in the Solar Nebula almost contemporary to the giant planets. The actual process producing the first generation of asteroids is uncertain, strongly depending on the physical characteristics of the Solar Nebula, and the different scenarios produce very diverse initial size-frequency distributions. In this work we investigate the implications of the formation of Jupiter, plausibly the first giant planet to form, on the evolution of the primordial asteroid belt. The formation of Jupiter triggered a short but intense period of primordial bombardment, previously unaccounted for, which caused an early phase of enhanced collisional evolution in the asteroid belt. Our results indicate that this Jovian Early Bombardment caused the erosion or the disruption of bodies smaller than a threshold size, which strongly depends on the size-frequency distribution of the primordial planetesimals. If the asteroid belt was dominated by planetesimals less than 100 km in diameter, the primordial bombardment would have caused the erosion of bodies smaller than 200 km in diameter. If the asteroid belt was instead dominated by larger planetesimals, the bombardment would have resulted in the destruction of bodies as big as 500 km.