For any cosmological constant Λ = −3/$l2$ < 0 and any $\alpha$ < 9/4, we find a Kerr-AdS spacetime ($M$, $gKAdS$), in which the Klein-Gordon equation $◻gKAdS$ ψ+$\alpha$/$l2$ψ = 0 has an exponentially growing mode solution satisfying a Dirichlet boundary condition at infinity. The spacetime violates the Hawking-Reall bound r$\mathrm{<mrow\; data-mjx-texclass="ORD">-+</mrow><mrow\; data-mjx-texclass="ORD">+2</mrow>}$ > |$a$|$l$. We obtain an analogous result for Neumann boundary conditions if 5/4 < $\alpha$ < 9/4. Moreover, in the Dirichlet case, one can prove that, for any Kerr-AdS spacetime violating the Hawking-Reall bound, there exists an open family of masses $\alpha$ such that the corresponding Klein-Gordon equation permits exponentially growing mode solutions. Our result adopts methods of Shlapentokh-Rothman developed in [SR13] and provides the first rigorous construction of a superradiant instability for negative cosmological constant.