Entanglement is a necessary resource for quantum applications--entanglement established between quantum systems at different locations enables private communication and quantum teleportation, and facilitates quantum information processing. Distributed entanglement is established by preparing an entangled pair of quantum particles in one location, and transporting one member of the pair to another location. However, decoherence during transport reduces the quality (fidelity) of the entanglement. A protocol to achieve entanglement 'purification' has been proposed to improve the fidelity after transport. This protocol uses separate quantum operations at each location and classical communication to distil high-fidelity entangled pairs from lower-fidelity pairs. Proof-of-principle experiments distilling entangled photon pairs have been carried out. However, these experiments obtained distilled pairs with a low probability of success and required destruction of the entangled pairs, rendering them unavailable for further processing. Here we report efficient and non-destructive entanglement purification with atomic quantum bits. Two noisy entangled pairs were created and distilled into one higher-fidelity pair available for further use. Success probabilities were above 35 per cent. The many applications of entanglement purification make it one of the most important techniques in quantum information processing.