Storage of quantum information encoded into heralded single photons is an essential constituent of long-distance quantum communication based on quantum repeaters and of optical quantum information processing. The storage of photonic polarization qubits is, however, difficult because many materials are birefringent and have polarization-dependent absorption. Here we present a simple scheme that eliminates these polarization effects, and we demonstrate it by storing heralded polarization qubits into a solid-state quantum memory. The quantum memory is implemented with a biaxial yttrium orthosilicate (Y2SiO5) crystal doped with rare-earth ions. Heralded single photons generated from a filtered spontaneous parametric down-conversion source are stored, and quantum state tomography of the retrieved polarization state reveals an average fidelity of 97.5±0.4%, which is significantly higher than what is achievable with a measure-and-prepare strategy.