We report combined optical and X-ray observations of nova M31N 2007-12b. Optical spectroscopy obtained 5 days after the 2007 December outburst shows evidence of very high ejection velocities (FWHM H$\alpha \simeq 4500$ km s$^{-1}$). In addition, Swift X-ray data show that M31N 2007-12b is associated with a Super-Soft Source (SSS) which appeared between 21 and 35 days post-outburst and turned off between then and day 169. Our analysis implies that $M_{\rm WD} \ga 1.3 $M$_{\odot}$ in this system. The optical light curve, spectrum and X-ray behaviour are consistent with those of a recurrent nova. Hubble Space Telescope observations of the pre-outburst location of M31N 2007-12b reveal the presence of a coincident stellar source with magnitude and color very similar to the Galactic recurrent nova RS Ophiuchi at quiescence, where the red giant secondary dominates the emission. We believe that this is the first occasion on which a nova progenitor system has been identified in M31. However, the greatest similarities of outburst optical spectrum and SSS behaviour are with the supposed Galactic recurrent nova V2491 Cygni. A previously implied association of M31N 2007-12b with nova M31N 1969-08a is shown to be erroneous and this has important lessons for future searches for recurrent novae in extragalactic systems. Overall, we show that suitable complementary X-ray and optical observations can be used not only to identify recurrent nova candidates in M31, but also to determine subtypes and important physical parameters of these systems. Prospects are therefore good for extending studies of recurrent novae into the Local Group with the potential to explore in more detail such important topics as their proposed link to Type Ia Supernovae.