We demonstrate a probabilistic entangling quantum gate between two distant trapped ytterbium ions. The gate is implemented between the hyperfine "clock" state atomic qubits and mediated by the interference of two emitted photons carrying frequency encoded qubits. Heralded by the coincidence detection of these two photons, the gate has an average output state fidelity of 89 +/- 2%. This entangling gate together with single qubit operations is sufficient to generate large entangled cluster states for scalable quantum computing.