The present paper considers the relation between microstructure characteristics of vacuum-deposited Fe100−xNix (30<x<39) foils and their mechanical properties. The foils 40–100μm thick with various microstructure characteristics were prepared using electron beam physical vapor deposition (EBPVD) onto substrates maintained at different temperatures in the 250–700°С range. The foil microhardness increases as deposition temperature decreases and reaches the maximum value of 5GPa for foils deposited at 300°C. It has been shown that the crystallite size in the foils decreases monotonically from sub-micron values (over 100nm) to nanoscaled ones (10–20nm), while the level of microstrains of FCC lattice increases to 1% with lowering deposition temperature. The dependence of foil microhardness on the crystallite size in the Hall–Petch’s coordinates (Hμ vs d−1/2) exhibits the deviation from a linear function at microhardness of 5GPa. Such behavior of the foil microhardness at decreasing deposition temperature correlates with an abrupt increase in both porosity and microstrains level.