Large-scale quantum computers will inevitably require quantum gate operations between widely separated qubits, even within a single quantum information processing device. Nearly two decades ago, Gottesman and Chuang proposed a method for implementing such operations, known as quantum gate teleportation (1). It requires only local operations on the remote qubits, classical communication, and shared entanglement that is prepared before the logical operation. Here we demonstrate this approach in a scalable architecture by deterministically teleporting a controlled-NOT (CNOT) gate between two computational qubits in spatially separated zones in a segmented ion trap. Our teleported CNOT's entanglement fidelity is in the interval [0.845, 0.872] at the 95% confidence level. The implementation combines ion shuttling with individually-addressed single-qubit rotations and detections, same- and mixed-species two-qubit gates, and real-time conditional operations, thereby demonstrating essential tools for scaling trapped-ion quantum computers combined in a single device.