The damage-tolerant titanium alloy TC21 is used extensively in important parts of advanced aircraft because of its high strength and durability. However, cutting TC21 entails problems, such as high cutting temperature, high tool tip stress, rapid tool wear, and difficulty guaranteeing processing quality. Orthogonal turn-milling can be used to solve these problems. In this study, the machinability of TC21 in orthogonal turn-milling is investigated experimentally to optimize the cutting parameters of orthogonal turn-milling and improve the machining efficiency, tool life, and machining quality of TC21. The mechanism of the effect of turn-milling parameters on tool life is discussed, the relationship between each parameter and tool life is analyzed, and the failure process of a TiAlN-coated tool in turn-milling is explored. Experiments are conducted on the integrity of the machined surface (surface roughness, metallographic structure, and work hardening) by turn-milling, and how the parameters influence such integrity is analyzed. Then, reasonable cutting parameters for TC21 in orthogonal turn-milling are recommended. This study provides strong guidance for exploring the machinability of difficult-to-cut-materials in orthogonal turn-milling and improves the applicability of orthogonal turn-milling for such materials.