We consider linear gravitational perturbations of the Kerr brane, an exact solution of vacuum Einstein's equations in dimensions higher than four and a low-energy solution of string theory. Decomposing the perturbations in tensor harmonics of the trans-verse Ricci-flat space, we show that tensor- and vector-type metric perturbations of the Kerr brane satisfy respectively a massive Klein-Gordon equation and a Proca equation on the four-dimensional Kerr space, where the mass term is proportional to the eigenvalue of the harmonics. Massive bosonic fields trigger a well-known superradiant instability on a Kerr black hole. We thus establish that Kerr branes in dimensions D a parts per thousand yen 6 are gravi-tationally unstable due to superradiance. These solutions are also unstable against the Gregory-Laflamme instability and we discuss the conditions for either instability to occur and their rather different nature. When the transverse dimensions are compactified and much smaller than the Kerr horizon, only the superradiant instability is present, with a time scale much longer than the dynamical time scale. Our formalism can be also used to discuss other types of higher-dimensional black objects, taking advantage of recent progress in studying linear perturbations of four-dimensional black holes.