Quantum information science involves the storage, manipulation and communication of information encoded in quantum systems, where the phenomena of superposition and entanglement can provide enhancements over what is possible classically. Large-scale quantum information processors require stable and addressable quantum memories, usually in the form of fixed quantum bits (qubits), and a means of transferring and entangling the quantum information between memories that may be separated by macroscopic or even geographic distances. Atomic systems are excellent quantum memories, because appropriate internal electronic states can coherently store qubits over very long timescales. Photons, on the other hand, are the natural platform for the distribution of quantum information between remote qubits, given their ability to traverse large distances with little perturbation. Recently, there has been considerable progress in coupling small samples of atomic gases through photonic channels, including the entanglement between light and atoms and the observation of entanglement signatures between remotely located atomic ensembles. In contrast to atomic ensembles, single-atom quantum memories allow the implementation of conditional quantum gates through photonic channels, a key requirement for quantum computing. Along these lines, individual atoms have been coupled to photons in cavities, and trapped atoms have been linked to emitted photons in free space. Here we demonstrate the entanglement of two fixed single-atom quantum memories separated by one metre. Two remotely located trapped atomic ions each emit a single photon, and the interference and detection of these photons signals the entanglement of the atomic qubits. We characterize the entangled pair by directly measuring qubit correlations with near-perfect detection efficiency. Although this entanglement method is probabilistic, it is still in principle useful for subsequent quantum operations and scalable quantum information applications.