Quantum teleportation1 is a cornerstone of quantum information science due to its essential role in important tasks such as the long-distance transmission of quantum information using quantum repeaters2, 3. This requires the efficient distribution of entanglement between remote nodes of a network4. Here, we demonstrate quantum teleportation of the polarization state of a telecom-wavelength photon onto the state of a solid-state quantum memory. Entanglement is established between a rare-earth-ion-doped crystal storing a single photon that is polarization-entangled with a flying telecom-wavelength photon5, 6. The latter is jointly measured with another flying polarization qubit to be teleported, which heralds the teleportation. The fidelity of the qubit retrieved from the memory is shown to be greater than the maximum fidelity achievable without entanglement, even when the combined distances travelled by the two flying qubits is 25 km of standard optical fibre. Our results demonstrate the possibility of long-distance quantum networks with solid-state resources.