This work reports an original approach to the synthesis of composite “core-shell” nanoparticles of o-EuFeO₃@am-EuFeO₃ via solution combustion synthesis (SCS) followed by heat treatment in the air. PXRD, ⁵⁷Fe and ¹⁵¹Eu Mössbauer spectroscopy, FTIR, DSC-TGA, SEM-EDX, TEM-SAED and vibrating-sample magnetometry were used to analyze the as-prepared and heat-treated samples. It was shown that the formation of amorphous am-EuFeO₃ “shell” on the surface of crystalline o-EuFeO₃ “cores” arises from the partial carbonatization of europium oxide during the solution combustion. It was found that the average crystallite size of o-EuFeO₃ “cores” (37–92 nm) and thickness of am-EuFeO₃ “shell” (1–10 nm) can be easily varied through the simple temperature change of heat treatment in the range of 500–900 °C. Acquired composite nanoparticles o-EuFeO₃@am-EuFeO₃ demonstrate uniform isometric morphology with a well distinct core and shell. Magnetometry results indicate the paramagnetic behavior of composite nanoparticles in a wide range of temperatures and applied magnetic fields that contradict the Mössbauer spectroscopy results showing the magnetic ordering of Fe-sublattice of o-EuFeO₃ “cores”. Thus, the results of this work confirm the possibility of obtaining a new class of rare earth orthoferrite nanomaterials with the core-shell structure that can have promising functional applications.