Magnetic resonance detection is one of the most important tools used in life-sciences today. However, as the technique detects the magnetization of large ensembles of spins it is fundamentally limited in spatial resolution to mesoscopic scales. Here we detect the natural fluctuations of nanoscale spin ensembles at ambient temperatures by measuring the decoherence rate of a single quantum spin in response to introduced extrinsic target spins. In our experiments 45 nm nanodiamonds with single nitrogen-vacancy (NV) spins were immersed in solution containing spin 5/2 Mn^2+ ions and the NV decoherence rate measured though optically detected magnetic resonance. The presence of both freely moving and accreted Mn spins in solution were detected via significant changes in measured NV decoherence rates. Analysis of the data using a quantum cluster expansion treatment of the NV-target system found the measurements to be consistent with the detection of ~2,500 motionally diffusing Mn spins over an effective volume of (16 nm)^3 in 4.2 s, representing a reduction in target ensemble size and acquisition time of several orders of magnitude over state-of-the-art electron spin resonance detection. These measurements provide the basis for the detection of nanoscale magnetic field fluctuations with unprecedented sensitivity and resolution in ambient conditions.