The orbital distribution of trans-Neptunian objects provides strong evidence for the radial migration of Neptune1,2. The outer planets’ orbits are thought to have become unstable during the early stages3, with Jupiter having scattering encounters with a Neptune-class planet4. As a consequence, Jupiter jumped inwards by a fraction of an au, as required from inner Solar System constraints5,6, and obtained its current orbital eccentricity. The timing of these events is often linked to the lunar Late Heavy Bombardment that ended ~700 Myr after the dispersal of the protosolar nebula (t0)7,8. Here, we show instead that planetary migration started shortly after t0. Such early migration is inferred from the survival of the Patroclus–Menoetius binary Jupiter Trojan9. The binary formed at t ≲ t010,11 within a massive planetesimal disk once located beyond Neptune12,13. The longer the binary stayed in the disk, the greater the likelihood that collisions would strip its components from one another. The simulations of its survival indicate that the disk had to have been dispersed by migrating planets within ≲100 Myr of t0. This constraint implies that the planetary migration is unrelated to the formation of the youngest lunar basins. The Patroclus–Menoetius Jupiter Trojan binary could survive its travel from the Kuiper belt to Jupiter’s orbit only if the giant planets’ migrations happened within ~100 Myr after the birth of the Solar System and not after ~700 Myr, as suggested instead by the Late Heavy Bombardment.