Titanium (Ti) has been widely used as a dental implant material due to its excellent mechanical property and good biocompatibility. However, its poor biological activity severely limits its ability to bond with bony tissues. To ameliorate this situation, a preparation method of ultra-high bonding nano-hydroxyapatite (n-HA) coating on the Ti surface is urgently needed. Here, Ti phosphate/n-HA (TiP-Ca) composite coatings with ultra-high bonding were prepared by a two-step hydrothermal treatment. The TiP coating was first formed in situ on the pure Ti substrate and then n-HA crystals further grew on the TiP surface. The formation mechanism of composite coating and reasons for increased bonding strength were systematically investigated. The results show that the TiP-Ca coating remains stable and exhibits an ultra-high bonding strength with the Ti implant (up to 783.30 ± 207.46 N). An effective solution was designed to address the problems of easy peel off. Cell experiments showed that TiP-Ca could promote the adhesion of MC3T3-E1 and expression of OCN, Runx2, and ALP. In vivo evaluation further confirmed that the TiP-Ca composite coating significantly enhanced osseointegration. The designed coating shows great potential in clinical application of implants.