The dominant gaseous structure in the Galactic halo is the Magellanic Stream. This extended network of neutral and ionized filaments surrounds the Large Magellanic Cloud (LMC) and the Small Magellanic Cloud (SMC), the two most massive satellite galaxies of the Milky Way(1-4). Recent observations indicate that the LMC and SMC are on their first passage around the Galaxy(5), that the Magellanic Stream is made up of gas stripped from both clouds(2,6,7) and that the majority of this gas is ionized(8,9). Although it has long been suspected that tidal forces(10,11) and ram-pressure stripping(12,13) contributed to the formation of the Magellanic Stream, models have not been able to provide a full understanding of its origins(3). Several recent developments-including the discovery of dwarf galaxies associated with the Magellanic group(14-16), determination of the high mass of the LMC17, detection of highly ionized gas near stars in the LMC18,19 and predictions of cosmological simulations(20,21)-support the existence of a halo of warm (roughly 500,000 kelvin) ionized gas around the LMC (the 'Magellanic Corona'). Here we report that, by including this Magellanic Corona in hydrodynamic simulations of the Magellanic Clouds falling onto the Milky Way, we can reproduce the Magellanic Stream and its leading arm. Our simulations explain the filamentary structure, spatial extent, radial-velocity gradient and total ionized-gas mass of the Magellanic Stream. We predict that the Magellanic Corona will be unambiguously observable via high-ionization absorption lines in the ultraviolet spectra of background quasars lying near the LMC.