Quantum physics forbids cloning of a qubit. Therefore, a qubit is irreversibly lost upon loss of the information carrier. To mitigate this physical loss, it has been proposed to distribute the logical information across an entangled set of physical qubits, some of which can be lost. Previous experiments illustrated this concept, but failed to demonstrate a gain in the information-retrieval efficiency. Here we address this challenge with photons for which the total loss, from generation to detection, is below the loss-tolerance threshold of $50\%$. Using two single-atom emitters in an optical cavity, we encode information into the photons of a graph state and observe an efficiency gain for retrieving quantum correlations between the atoms and the photons for single-qubit measurements in the Pauli $X$ and $Z$ bases. Although technical errors reduce the probability to obtain the result, we achieve average fidelities as high as $\gtrsim 70\%$ without and $\gtrsim 75\%$ with error detection, demonstrating entanglement between the atomic and encoded photonic qubits. Lowering the encoding errors is a next natural step toward loss-tolerant photonic quantum-information processing.