The aim of this study was to investigate the damage of cutting tools coated by physical vapor deposition (PVD) during the continuous turning of a titanium alloy. The investigation utilized scanning electron microscopy (SEM), electron probe micro-analysis (EPMA), and transmission electron microscopy (TEM). It was found that a TiN coating on the tool wore faster than an uncoated cemented carbide tool. The damage mode of the coating on the rake face was fracture without plastic deformation. Additionally, there was a pattern to the crystal orientation relationship at some of the interfaces between the adhered workpiece material and the TiN coating. The crystal orientation relationship presumably produced a strong bond between the adhered material and the coating. The coating damage was thus caused by the force exerted by the adhered materials on the grain boundary on the damaged coating surface. A comparison of the tool damages during the machining of Ti-6Al-4V alloy and alloy 718 suggested that the damage of the coating depended on the interfacial strength between the adhered material and the coating, as well as the strength of the adhered material at a high temperature. Hence, to prevent the damage of the tool during the machining of a titanium alloy, it is preferable to use a ductile material (e.g., cemented carbide) rather than a brittle material (e.g., ceramic).