Ultra-class mining trucks used for material haulage in rugged surface mining terrains experience premature tire fatigue failure in operation. Typical failures include belt edge separation, ply turn-up separation, and tread base and sidewall cracking. The use of reinforcing fillers and processing aids in tire compounds result in the formation of microstructural in-homogeneities in the compounds. This article presents an application of the critical plane analysis technique for predicting the fatigue life of the belt package of an ultra-large mining truck (CAT 795F) tire of size 56/80R63 in a surface coal mine. Experimental data obtained from extracted specimens (sidewall, tread, and belt edge region) of the tire are used to characterize the stress—strain and fatigue behavior of the modeled tire. The tire's duty cycle stresses and strains were obtained from finite element analysis of the rolling tire in Abaqus. Fatigue life calculations were performed in the rubber fatigue solver Endurica CL. Effects of inflation pressure, tire speed, and axle load on the fatigue life of the belt package under strain-crystallizing and non-crystallizing conditions of the belt compound are discussed. Specifically, the results show the belt edges to be critical regarding crack nucleation.