We present the first example of a linearized gravitational instability of an asymptotically flat vacuum black hole: the ultraspinning instability first conjectured to exist by Emparan and Myers. We study perturbations of a Myers-Perry black hole 1) with a single spin and 2) with equal angular momenta. In the singly spinning case we find the stationary perturbations that mark the onset of the instability and the appearance of the new pinched black hole phases that are conjectured to connect to the black ring and black Saturn families. We further analyse the asymptotically AdS case, and determine the onset of the instability as a function of the cosmological constant. For the equal spin case, we find perturbations that grow exponentially in time and the dispersion relation of the instability. The onset of the instability is associated with the appearance of time-independent perturbations which generically break all but one of the rotational symmetries. This is interpreted as evidence for the existence of a new 20-parameter family of black hole solutions with only a single rotational symmetry, ie that saturate Hawking's rigidity theorem. We also present results for the Gregory-Laflamme instability of rotating black strings, demonstrating for the first time that rotation makes black strings more unstable. Finally, we establish a formal connection between this classical instability and thermodynamics that provides a "thermodynamic candle" to anticipate the possible existence of this instability in other black holes.