We present the first example of a linearized gravitational instability of an asymptotically flat vacuum black hole. We study perturbations of a Myers-Perry black hole with equal angular momenta in an odd number of dimensions. We find no evidence of any instability in five or seven dimensions, but in nine dimensions, for sufficiently rapid rotation, we find perturbations that grow exponentially in time. The onset of 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 70-parameter family of black hole solutions with only a single rotational symmetry. We also present results for the Gregory-Laflamme instability of rotating black strings, demonstrating that rotation makes black strings more unstable.