Understanding the dynamics of a quantum bit's environment is essential for the realization of practical systems for quantum information processing and metrology. We use single nitrogen-vacancy (NV) centers in diamond to study the dynamics of a disordered spin ensemble at the diamond surface. Specifically, we reduce the density of "dark"surface spins to interrogate their contribution to the decoherence of shallow NV center spin qubits. When the average surface spin spacing exceeds the NV center depth, we find that the surface spin contribution to the NV center free induction decay can be described by a stretched exponential with variable power n. We show that these observations are consistent with a model in which the spatial positions of the surface spins are fixed for each measurement, but some of them reconfigure between measurements. In particular, we observe a depth-dependent critical time associated with a dynamical transition from Gaussian (n=2) decay to n=2/3, and show that this transition arises from the competition between the small decay contributions of many distant spins and strong coupling to a few proximal spins at the surface. These observations demonstrate the potential of a local sensor for understanding complex systems and elucidate pathways for improving and controlling spin qubits at the surface.