AdS/CFT provides a consistent non-perturbative definition of quantum gravity in asymptotically AdS space. Black holes should correspond to ensembles of states in the boundary field theory. By analyzing the superconformal index of 4d N=4 SU(N) Super-Yang-Mills, with the help of a new Bethe Ansatz type formula, we are able to exactly reproduce the Bekenstein-Hawking entropy of BPS black holes in AdS5 x S5. The large N limit exhibits many competing contributions and Stokes phenomena, hinting at new physics.