The steady increase in control over individual quantum systems supports the promotion of a quantum technology that could provide functionalities beyond those of any classical device. Two particularly promising applications have been explored during the past decade: photon-based quantum communication, which guarantees unbreakable encryption(1) but which still has to be scaled to high rates over large distances, and quantum computation, which will fundamentally enhance computability(2) if it can be scaled to a large number of quantum bits (qubits). It was realized early on that a hybrid system of light qubits and matter qubits(3) could solve the scalability problem of each field-that of communication by use of quantum repeaters4, and that of computation by use of an optical interconnect between smaller quantum processors(5,6). To this end, the development of a robust two-qubit gate that allows the linking of distant computational nodes is "a pressing challenge"(6). Here we demonstrate such a quantum gate between the spin state of a single trapped atom and the polarization state of an optical photon contained in a faint laser pulse. The gate mechanism presented(7,8) is deterministic and robust, and is expected to be applicable to almost any matter qubit. It is based on reflection of the photonic qubit from a cavity that provides strong light-matter coupling. To demonstrate its versatility, we use the quantum gate to create atom-photon, atom-photon-photon and photon-photon entangled states from separable input states. We expect our experiment to enable various applications, including the generation of atomic(9) and photonic(10) cluster states and Schrodinger-cat states(11), deterministic photonic Bell-state measurements(12), scalable quantum computation(7) and quantum communication using a redundant quantum parity code(13).