Recently nanocrystalline Al-Fe alloys produced by a vapor quench method have been reported. These alloys are supersaturated solid solution and exhibit high strength with good ductility. It is postulated that the high strength of the Al-Fe alloys could be achieved by both the nano-grained structures and the solid solution strengthening. The contribution to the yield strength due to both the grain size strengthening and the solid solution strengthening were analyzed from the experimental data. Then the contribution to the yield strength due to the solid solution strengthening was estimated from the misfit strain calculated from the first principles in order to compare with analytical results estimated from the experimental data.