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 fidelity of 90+-2%. This entangling gate together with single qubit operations is sufficient to generate large entangled cluster states for scalable quantum computing.