Elucidating the relationship between internal strain and structural modification of metal oxide nanostructures expands our ability to fine tune their physical properties. However, this aspect of strain engineering is still challenging. Here, we employed two-step solution chemistry and prepared cube nanostructures Ce1–yFeyO2 with high sample uniformity. The solubility limit for Fe3+ ions doped in CeO2 nanostructures is determined to be around y = 0.15. Below the solubility limit, cube nanostructures showed a pronounced tensile strain that increased almost linearly with the doping levels. This tensile strain did not destroy the fluorite structure of parent CeO2 nanostructures but resulted in the smallest lattice constant ever reported for all CeO2-based solid solutions. In spite of a large change in lattice parameters, Raman phonon modes for these solid solutions did not shift at all with the strain, which differs from those under external compression or size effects. Further increasing the strain led to a magnetic transition of cube nanocrystals Ce1–yFeyO2 from the very weak paramagnetic to coexistence of paramagnetic and ferromagnetic components. Results reported in this work demonstrate that strain engineering is the base for intrinsic control over the structures and magnetic properties of metal oxide nanostructures and therefore may find many applications in spintronics and other devices.