Photonic interconnects between quantum processing nodes are likely the only way to achieve large-scale quantum computers and networks (1). The bottleneck in such an architecture is the interface between well-isolated quantum memories and flying photons. We establish high-fidelity entanglement between remotely separated trapped atomic qubit memories (2–4), mediated by photonic qubits stored in the timing of their pulses (5). Such time-bin encoding removes sensitivity to polarization errors, enables long-distance quantum communication, and is extensible to quantum memories with more than two states. Using a measurementbased error detection process and suppressing a fundamental source of error due to atomic recoil, we achieve an entanglement fidelity of 97% and show that fidelities beyond 99.9% are feasible.