We report the results of a survey of M31 novae in quiescence. This is the first catalog of extragalactic systems in quiescence to be published, and contains data for 38 spectroscopically confirmed novae from 2006 to 2012. We used Liverpool Telescope (LT) images of each nova during eruption to define an accurate position for each system. These positions were then matched to archival Hubble Space Telescope (HST) images and we performed photometry on any resolved objects that were coincident with the eruption positions. The survey aimed to detect quiescent systems with red giant secondaries, as only these, along with a few systems with bright sub-giant secondaries, will be resolvable in the HST images. There are only a few confirmed examples of such red giant novae in our Galaxy, the majority of which are recurrent novae. However, we find a relatively high percentage of the nova eruptions in M31 may occur in systems containing red giant secondaries. Of the 38 systems in this catalog, 11 have a progenitor candidate whose probability of being a coincidental alignment is less than 5%. We show that, at the 3 sigma limit, up to only two of these eleven systems may be due to chance alignments, leading to an estimate of the M31 nova population with evolved secondaries of up to 24%, compared to the ~3% seen Galactically. Such an elevated proportion of nova systems with evolved secondaries may imply the presence of a much larger population of recurrent novae than previously thought. This would have considerable impact, particularly with regards their potential as Type Ia supernova progenitors.