We demonstrate quantum entanglement of two trapped atomic ion qubits using a sequence of ultrafast laser pulses. Unlike previous demonstrations of entanglement mediated by the Coulomb interaction, this scheme does not require confinement to the Lamb-Dicke regime and can be less sensitive to ambient noise due to its speed. To elucidate the physics of an ultrafast phase gate, we generate a high entanglement rate using just ten pulses, each of similar to 20 ps duration, and demonstrate an entangled Bell state with (76 +/- 1)% fidelity. These results pave the way for entanglement operations within a large collection of qubits by exciting only local modes of motion.