We have performed a wide-area ultraviolet (UV) imaging survey using the GALaxy Evolution eXplorer to search for bright, point-like UV sources behind M31's extended halo. Our survey consisted of 46 pointings covering an effective area of ~50deg^2^, in both the far-UV and near-UV channels. We combined these data with optical R-band observations acquired with the WIYN Mosaic-1 imager on the Kitt Peak National Observatory 0.9-m WIYN telescope. An analysis of the brightness and colours of sources matched between our photometric catalogues yielded ~100 UV-bright quasar candidates. We have obtained discovery spectra for 76 of these targets with the Kast spectrometer on the Lick 3-m telescope and confirmed 30 active galactic nuclei and quasars, 29 galaxies at z>0.02 including several early-type systems, 16 Galactic stars (hot main-sequence stars) and one featureless source previously identified as a BL Lac object. Future UV spectroscopy of the brightest targets with the Cosmic Origins Spectrograph on the Hubble Space Telescope will enable a systematic search for diffuse gas in the extended halo of M31.