Atomically sharp oxide heterostructures exhibit a range of novel physical phenomena that do not occur in the parent bulk compounds. The most prominent example is the appearance of highly conducting and superconducting states at the interface between the band insulators LaAlO3 and SrTiO3. Here we report a new emergent phenomenon at the LaMnO3/SrTiO3 interface in which an antiferromagnetic insulator abruptly transforms into a magnetic state that exhibits unexpected nanoscale superparamagnetic dynamics. Upon increasing the thickness of LaMnO3 above five unit cells, our scanning nanoSQUID-on-tip microscopy shows spontaneous formation of isolated magnetic islands of 10 to 50 nm diameter, which display random moment reversals by thermal activation or in response to an in-plane magnetic field. Our charge reconstruction model of the polar LaMnO3/SrTiO3 heterostructure describes the sharp emergence of thermodynamic phase separation leading to nucleation of metallic ferromagnetic islands in an insulating antiferromagnetic matrix. The model further suggests that the nearby superparamagnetic-ferromagnetic transition can be gate tuned, holding potential for applications in magnetic storage and spintronics.