The interplay between superconductivity and magnetism gives rise to many intriguing and exciting phenomena. In this Letter we report about a novel manifestation of this interplay: a temperature induced phase transition between different spontaneous vortex phases in lead superconducting films with embedded magnetic nanoparticles. Unlike common vortices in superconductors the vortex phase appears without any applied magnetic field. The vortices nucleate exclusively due to the stray field of the magnetic nanoparticles, which serve the dual role of providing the internal field and simultaneously acting as pinning centers. As in usual superconductors, one can move the spontaneous vortices with an applied electric current. Transport measurements reveal dynamical phase transitions that depend on temperature (T) and applied field (H) and support the obtained (H-T) phase diagram. In particular, we used a scaling analysis to characterize a transition from a liquid to a novel disordered solid resembling a vortex glass.