We show that bulk nanocrystalline Ni4Mo can be synthesized by doping with small but critical concentrations of Y. Two alloys are included in the study with compositions of Ni4Mo and Ni4Mo + 0.01 wt% Y. Microstructural features derived from transmission electron microscopy observations are correlated with room-temperature tensile properties. Yttrium-doped Ni4Mo is found to have room-temperature yield strength in excess of 800 MPa and tensile elongation to failure of about 40% while simultaneously retaining other useful physical and chemical properties of intermetallic compounds. Twinning rather than slip is found to be the predominant deformation mechanism, which is correlated with the superlattice structure of Ni4Mo. Since deformation by twinning is polarized, this is expected to enhance the fatigue life.