We demonstrate the generation of rubidium-resonant heralded single photons for quantum memories. Photon pairs are created by cavity-enhanced down-conversion and narrowed in bandwidth to 7 MHz with a novel atom-based filter operating by "interaction-free measurement" principles. At least 94% of the heralded photons are atom-resonant as demonstrated by a direct absorption measurement with rubidium vapor. A heralded autocorrelation measurement shows g(c)(2)(0)=0.040±0.012, i.e., suppression of multiphoton contributions by a factor of 25 relative to a coherent state. The generated heralded photons can readily be used in quantum memories and quantum networks.