The accretion of hydrogen onto a white dwarf star ignites a classical nova eruption1,2—a thermonuclear runaway in the accumulated envelope of gas, leading to luminosities up to a million times that of the Sun and a high-velocity mass ejection that produces a remnant shell (mainly consisting of insterstellar medium). Close to the upper mass limit of a white dwarf3 (1.4 solar masses), rapid accretion of hydrogen (about 10-7 solar masses per year) from a stellar companion leads to frequent eruptions on timescales of years4,5 to decades6. Such binary systems are known as recurrent novae. The ejecta of recurrent novae, initially moving at velocities of up to 10,000 kilometres per second7, must `sweep up' the surrounding interstellar medium, creating cavities in space around the nova binary. No remnant larger than one parsec across from any single classical or recurrent nova eruption is known8-10, but thousands of successive recurrent nova eruptions should be capable of generating shells hundreds of parsecs across. Here we report that the most frequently recurring nova, M31N 2008-12a in the Andromeda galaxy (Messier 31 or NGC 224), which erupts annually11, is indeed surrounded by such a super-remnant with a projected size of at least 134 by 90 parsecs. Larger than almost all known remnants of even supernova explosions12, the existence of this shell demonstrates that the nova M31N 2008-12a has erupted with high frequency for millions of years.