Despite theoretical predictions for a Cherenkov-type radiation of spin waves (magnons) by various propagating magnetic perturbations, fast-enough moving magnetic field stimuli have not been available so far. Here, we experimentally realize the Cherenkov radiation of spin waves in a Co-Fe magnonic conduit by fast-moving (>1 km/s) magnetic flux quanta (Abrikosov vortices) in an adjacent Nb-C superconducting strip. The radiation is evidenced by the microwave detection of spin waves propagating a distance of 2 micrometers from the superconductor and it is accompanied by a magnon Shapiro step in its current-voltage curve. The spin-wave excitation is unidirectional and monochromatic, with sub-40 nm wavelengths determined by the period of the vortex lattice. The phase-locking of the vortex lattice with the excited spin wave limits the vortex velocity and reduces the dissipation in the superconductor.