We study the spontaneous breaking of rotational symmetry in the helical surface state of three-dimensional topological insulators due to strong electron-electron interactions, focusing on time-reversal invariant nematic order. Owing to the strongly spin-orbit coupled nature of the surface state, the nematic order parameter is linear in the electron momentum and necessarily involves the electron spin, in contrast with spin-degenerate nematic Fermi liquids. For a chemical potential at the Dirac point (zero doping), we find a first-order phase transition at zero temperature between isotropic and nematic Dirac semimetals. This extends to a thermal phase transition that changes from first to second order at a finite-temperature tricritical point. At finite doping, we find a transition between isotropic and nematic helical Fermi liquids that is second order even at zero temperature. Focusing on finite doping, we discuss various observable consequences of nematic order, such as anisotropies in transport and the spin susceptibility, the partial breakdown of spin-momentum locking, collective modes and induced spin fluctuations, and non-Fermi-liquid behavior at the quantum critical point and in the nematic phase.