A charged particle moving through a medium emits Cherenkov radiation when its velocity exceeds the phase velocity of light in that medium. Under the influence of a strong electromagnetic field, quantum fluctuations can become polarized, imbuing the vacuum with an effective anisotropic refractive index and allowing the possibility of Cherenkov radiation from the quantum vacuum. We analyze the properties of this vacuum Cherenkov radiation in strong laser pulses and the magnetic field around a pulsar, finding regimes in which it is the dominant radiation mechanism. This radiation process may be relevant to the excess signals of high energy photons in astrophysical observations.