We study the linear stability of asymptotically anti-de Sitter black holes in general relativity in spacetime dimension $d>4$. Our approach is an adaptation of the general framework of Hollands and Wald, which gives a stability criterion in terms of the sign of the canonical energy, $\mathcal{E}$. The general framework was originally formulated for static or stationary and axisymmetric black holes in the asymptotically flat case, and the stability analysis for that case applies only to axisymmetric perturbations. However, in the asymptotically anti-de Sitter case, the stability analysis requires only that the black hole have a single Killing field normal to the horizon and there are no restrictions on the perturbations (apart from smoothness and appropriate behavior at infinity). For an asymptotically anti-de Sitter black hole, we define an ergoregion to be a region where the horizon Killing field is spacelike; such a region, if present, would normally occur near infinity. We show that for black holes with ergoregions, initial data can be constructed such that $\mathcal{E} < 0$, so all such black holes are unstable. To obtain such initial data, we first construct an approximate solution to the constraint equations using the WKB method, and then we use the Corvino-Schoen technique to obtain an exact solution. We also discuss the case of charged asymptotically anti-de Sitter black holes with generalized ergoregions.