Over the last several years, it has been shown that black hole microstate level statistics in various models of 2D gravity are encoded in wormhole amplitudes. These statistics quantitatively agree with predictions of random matrix theory for chaotic quantum systems; this behavior is realized since the 2D theories in question are dual to matrix models. But what about black hole microstate statistics for Einstein gravity in 3D and higher spacetime dimensions, and ultimately in non-perturbative string theory? We will discuss progress in these directions. In 3D, we compute a wormhole amplitude that encodes the energy level statistics of BTZ black holes. In 4D and higher, we find analogous wormholes which appear to encode the level statistics of small black holes just above threshold. Finally, we study analogous Euclidean wormholes in the low-energy limit of type IIB string theory; we provide evidence that they encode the level statistics of small black holes just above threshold in AdS5 x S5. Remarkably, these wormholes appear to be stable in appropriate regimes, and dominate over brane-anti-brane nucleation processes in the computation of black hole microstate statistics.