For over 80 years of research, the conventional description of free-electron radiation phenomena, such as Cherenkov radiation, has remained unchanged: classical three-dimensional electromagnetic waves. Interestingly, in reduced dimensionality, the properties of free-electron radiation are predicted to fundamentally change. Here, we present the first observation of Cherenkov surface waves, wherein free electrons emit narrow-bandwidth photonic quasiparticles propagating in two-dimensions. The low dimensionality and narrow bandwidth of the effect enable to identify quantized emission events through electron energy loss spectroscopy. Our results support the recent theoretical prediction that free electrons do not always emit classical light and can instead become entangled with the photons they emit. The two-dimensional Cherenkov interaction achieves quantum coupling strengths over two orders of magnitude larger than ever reported, reaching the single-electron-single-photon interaction regime for the first time with free electrons. Our findings pave the way to previously unexplored phenomena in free-electron quantum optics, facilitating bright, free-electron-based quantum emitters of heralded Fock states.