Quantum memories, for storing then retrieving photonic quantum states on demand, are crucial components for scalable quantum technologies. Spontaneous parametric downconversion (SPDC) with a nonlinear crystal is the most widely used process for generating entangled photon pairs or heralded single photons. Despite the desirability of efficient quantum memories for SPDC-generated single photons, the storage and retrieval efficiencies achieved with this approach still fall below 50%, a threshold value for practical applications. Here, we report an efficiency of > 70% for the storage of heralded single photons generated by cavity-enhanced SPDC using atomic quantum memories based on electromagnetically induced transparency (EIT). In addition, we demonstrate the quantum memory for single-photon polarization qubits with a fidelity of ∼96%. This result paves the way towards the development of large-scale quantum networks.