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 10 pulses, each of $sim20$ ps duration, and demonstrate an entangled Bell-state with $(76pm1)$% fidelity. These results pave the way for entanglement operations within a large collection of qubits by exciting only local modes of motion.