Recent theoretical and experimental studies indicate that strain relaxations induced at a substrate can substantially affect the shape of nanostructures during thin-film epitaxy. We reveal the influence of strain relaxations on the self-ordering of Fe adatoms on Cu(111) during low-temperature submonolayer deposition by complementary experimental and theroetical investigations. Combining kinetic Monte Carlo and first-principles density-functional theory calculations, we study the interplay between surface nanostructuring and strain relaxations at the Cu substrate. The comparison of our theoretical results with scanning tunneling microscopy observations reveals marked effects on the adatom nucleation because of the substrate strain relief. The modified energy landscape around Fe adatoms and small close-packed Fe clusters at short distances (<6 Å) opens up a slippage motion channel mediating the formation of iron dimers and compact aggregates.