In this work Ni-free austenitic stainless steels with nanostructure and their nanocomposites were synthesized by mechanical alloying (MA), heat treatment and nitriding of elemental microcrystalline Fe, Cr, Mn and Mo powders with addition of hydroxyapatite (HA). Microhardness and corrosion tests' results of obtained materials are presented. Mechanical alloying and nitriding are very effective technologies to improve the corrosion resistance of stainless steel. Decreasing the corrosion current density is a distinct advantage for prevention of ion release and it leads to better cytocompatibility. Similar process in case of nanocomposites of stainless steel with hydroxyapatite helps achieve even better mechanical properties and corrosion resistance. Hence nanocrystalline nickel-free stainless steels and nickel-free stainless steel/hydroxyapatite nanocomposites could be promising bionanomaterials for use as a hard tissue replacement implants, e.g. orthopedic implants.