It has been conjectured that higher-dimensional rotating black holes become unstable at a sufficiently large value of the rotation, and that new black holes with pinched horizons appear at the threshold of the instability. We search numerically and find the stationary axisymmetric perturbations of Myers-Perry black holes with a single spin that mark the onset of the instability and the appearance of the new black hole phases. We also find new ultraspinning Gregory-Laflamme instabilities of rotating black strings and branes.