With their very low density, excellent biocompatibility, and good mechanochemical properties, titanium alloys have been considered a high-end material for making biomedical devices and instruments. However, they still have some substantial challenges to be overcome. One major problem, which eventually leads to revision surgery, is the implant loosening- a result of tissue migration, formation of wear debris, insufficient interface bonding between bone and implant, and stress shielding. Nanosized features in the material have the potential to provide a solution to these problems. A nanostructured surface is able to not only promote tissue ingrowth, but also increase the surface hardness and therefore improving the wear resistance and enhancing fatigue strength. This paper reports our recent work on how surface treatment on titanium alloys changes their mechanical properties. The mechanism by which the surface nanostructuring alters mechanical properties has also been discussed.