The effects of nanostructuring on the mechanical and dry-sliding wear behaviors of a FeCoNi medium- entropy alloy (MEA) were systematically investigated through nano-indentation and ball-on-disc wear tests. The results show that reducing the grain size down into the nano-meter regime, on the one hand, significantly elevates the hardness of the FeCoNi alloy, and on the other hand, facilitates the formation of a surface oxide layer. As a result, the wear rate of the nanocrystalline (NC) FeCoNi alloy is one order of magnitude lower than its coarse-grained counterpart. The NC FeCoNi alloy also exhibits obviously enhanced wear resistance compared with conventional NC Ni and Ni-based alloys in terms of both lower wear rate and friction coefficient. Such enhancement in tribological properties mainly stems from the improved strain hardening ability, owing to the inevitable concentration heterogeneity in MEA that imposes extra resistance to dislocation motion.