For titanium alloys in high-temperature tribological contacts, titanium aluminum nitride (TiAlN) based coatings have proven to be an effective surface strengthening technique. However, there are conflicting results on how the deposition of such a ceramic coating affects the fatigue behavior of the underlying metallic titanium substrate. To address these shortcomings, a comprehensive study of two different synthesis approaches (varying stress states and an adapted alloying strategy for the coating material) was performed using a dynamic mechanical analyzer in a single cantilever configuration. As a result, the high-cycle fatigue limit of the material pairing was improved by up to 50% compared to the uncoated titanium alloy.