Quantum bits (qubits) based on individual trapped atomic ions are a promising technology for building a quantum computer. The elementary operations necessary to do so have been achieved with the required precision for some error-correction schemes. However, the essential two-qubit logic gate that is used to generate quantum entanglement has hitherto always been performed in an adiabatic regime (in which the gate is slow compared with the characteristic motional frequencies of the ions in the trap), resulting in logic speeds of the order of 10 kilohertz. There have been numerous proposals of methods for performing gates faster than this natural ‘speed limit’ of the trap. Here we implement one such method, which uses amplitude-shaped laser pulses to drive the motion of the ions along trajectories designed so that the gate operation is insensitive to the optical phase of the pulses. This enables fast (megahertz-rate) quantum logic that is robust to fluctuations in the optical phase, which would otherwise be an important source of experimental error. We demonstrate entanglement generation for gate times as short as 480 nanoseconds—less than a single oscillation period of an ion in the trap and eight orders of magnitude shorter than the memory coherence time measured in similar calcium-43 hyperfine qubits. The power of the method is most evident at intermediate timescales, at which it yields a gate error more than ten times lower than can be attained using conventional techniques; for example, we achieve a 1.6-microsecond-duration gate with a fidelity of 99.8 per cent. Faster and higher-fidelity gates are possible at the cost of greater laser intensity. The method requires only a single amplitude-shaped pulse and one pair of beams derived from a continuous-wave laser. It offers the prospect of combining the unrivalled coherence properties, operation fidelities and optical connectivity of trapped-ion qubits with the submicrosecond logic speeds that are usually associated with solid-state devices.