We have obtained nanostructured hydroxyapatite thin films on titanium alloy substrates by pulsed laser deposition. Deposition was carried out using a KrF excimer laser (248 nm) with the energy density of 4 – 7 J/cm2 at substrate temperatures in the 550°C - 650°C range. The crystallinity of the coatings was probed by X-ray diffraction. Phase transitions from hydroxyapatite to other calcium phosphate compounds were observed with varying the substrate temperature during the growth process. Scanning electron microscopy revealed thin films made up of partially sintered nanoscale grains. The average size of nanoscale grains increased significantly with film thickness, suggesting a growth mechanism involving the coalescence of nanoscale grains. As the laser energy density increases, the hydroxyapatite crystallites in the coatings are oriented preferentially along the c-axis perpendicular to the substrate. Mechanical properties of the highly c-axis oriented coatings such as hardness and Young's modulus were studied by using nanoindentation technique.