AdS/CFT provides a consistent non-perturbative definition of quantum gravity in asymptotically AdS spacetimes. Black holes correspond to ensembles of states in the boundary field theory. In the presence of supersymmetry, we rephrase the problem of counting those states in terms of a supersymmetric partition function: the superconformal index. By performing a careful analysis of the index of 4d N=4 SU(N) Super-Yang-Mills theory, with the help of a Bethe Ansatz approach, 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, that we are able to identify with complex saddles of the (putative) gravitational path-integral. Along the way we propose a necessary condition for complex saddles to contribute, based on the size of their non-perturbative corrections.