The present work deals with the effect of crystallite size on the hardness and fatigue life of steel samples coated with electrodeposited nanocrystalline Ni-W alloys. The Ni-W alloys were electrodeposited on steel samples at four different current densities (0.05, 0.10. 0.15 and 0.20 A/cm2) and at a temperature of 75 °C. The crystallite size of the deposit reduced (from 40 to 13 nm) with an increase in current density (from 0.05 to 0.20 A/cm2) due to an increase in the tungsten content (from 0.72 to 9.33 at.%). Ni-W alloy containing 9.33 at.% W and having a crystallite size of 13 nm exhibited the maximum hardness of 638 HV. The alloys, with the crystallite size in the range 40-13 nm, followed the direct Hall-Petch relation, i.e. hardness increased with a reduction in the crystallite size. The coated samples exhibited inferior fatigue lives compared to uncoated samples. This may be attributed to the presence of tensile residual stresses and inherent microcracks in the coatings. Among the specimens coated with Ni-W alloys, as the crystallite size decreased, the fatigue life of the specimen increased owing to the increase in hardness values. © 2006 Elsevier B.V. All rights reserved.