Fatigue is considered to be one of the most frequent phenomena in the failure of many machine parts. Most of the prior studies on fatigue have been limited to uniaxial loading cases with a primary focus on constant amplitude cycles. A detailed exploration of multiaxial fatigue under constant and variable amplitude loading scenarios for a wide variety of aircraft engine alloys has been performed in this study, and a new methodology for the accurate prediction of fatigue damage is developed. A critical-plane based constant amplitude fatigue damage model has been developed in this study which is simple in comparison to prior models developed by other researchers and reduces the computational effort. The constant amplitude fatigue damage model is further used in the development of a multiaxial variable amplitude damage estimation method, with an emphasis on estimating the damage created by both low cycle fatigue (LCF) and high cycle fatigue (HCF) cycles. A significant increase in overall fatigue damage was observed in the tests with the introduction of HCF cycles in the mission histories. The damage due to the HCF cycles has been found to be much greater than predicted by linear damage accumulation theories, although the degree of interaction between the LCF and HCF cycles was found to be very dependent on the multiaxial load paths. In addition, the HCF cycles did not contribute significantly to the accumulation of damage until a certain amount of “pre-damage” had been caused by the LCF cycles. Separate HCF damage computing approaches have been adopted in this study to accurately compute the damage produced by tensile and shear dominant HCF cycles, and a significant improvement in the accuracy of fatigue life prediction has been achieved using the new methodology.