Producing quantum states at random has become increasingly important in modern quantum science, with applications being both theoretical and practical. In particular, ensembles of such randomly distributed, but pure, quantum states underlie our understanding of complexity in quantum circuits and black holes , and have been used for benchmarking quantum devices in tests of quantum advantage . However, creating random ensembles has necessitated a high degree of spatio-temporal control placing such studies out of reach for a wide class of quantum systems. Here we solve this problem by predicting and experimentally observing the emergence of random state ensembles naturally under time-independent Hamiltonian dynamics, which we use to implement an efficient, widely applicable benchmarking protocol. The observed random ensembles emerge from projective measurements and are intimately linked to universal correlations built up between subsystems of a larger quantum system, offering new insights into quantum thermalization . Predicated on this discovery, we develop a fidelity estimation scheme, which we demonstrate for a Rydberg quantum simulator with up to 25 atoms using fewer than 10 experimental samples. This method has broad applicability, as we demonstrate for Hamiltonian parameter estimation, target-state generation benchmarking, and comparison of analogue and digital quantum devices. Our work has implications for understanding randomness in quantum dynamics and enables applications of this concept in a much wider context .