Photonic interconnects between quantum processing nodes are likely the only way to achieve large-scale quantum computers and networks. 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, mediated by photonic qubits stored in the timing of their pulses. 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 measurement-based error detection process and suppressing a fundamental source of error due to atomic recoil, we achieve an entanglement fidelity of 97% and show that fundamental limits due to atomic recoil still allow fidelities in excess of 99.9%.