Strong quantum confinement in semiconductors can compress the wavefunctions of band electrons and holes to nanometre-scale volumes, significantly enhancing interactions between themselves and individual dopants. In magnetically doped semiconductors, where paramagnetic dopants (such as Mn(2+), Co(2+) and so on) couple to band carriers via strong sp-d spin exchange, giant magneto-optical effects can therefore be realized in confined geometries using few or even single impurity spins. Importantly, however, thermodynamic spin fluctuations become increasingly relevant in this few-spin limit. In nanoscale volumes, the statistical fluctuations of N spins are expected to generate giant effective magnetic fields Beff, which should dramatically impact carrier spin dynamics, even in the absence of any applied field. Here we directly and unambiguously reveal the large Beff that exist in Mn(2+)-doped CdSe colloidal nanocrystals using ultrafast optical spectroscopy. At zero applied magnetic field, extremely rapid (300-600 GHz) spin precession of photoinjected electrons is observed, indicating Beff ∼ 15 -30 T for electrons. Precession frequencies exceed 2 THz in applied magnetic fields. These signals arise from electron precession about the random fields due to statistically incomplete cancellation of the embedded Mn(2+) moments, thereby revealing the initial coherent dynamics of magnetic polaron formation, and highlighting the importance of magnetization fluctuations on carrier spin dynamics in nanomaterials.