In this study, we explored the evolution of mechanical properties in hydroxyl-terminated polybutadiene (HTPB) propellants under fatigue loading by performing fatigue tests with varying maximum stresses and cycle numbers, followed by uniaxial tensile tests on post-fatigue specimens. Residual elongation was used as a key parameter to characterize mechanical behavior, while scanning electron microscopy (SEM) provided insights into the mesostructural morphological changes that occur under different loading conditions, revealing the mechanisms responsible for variations in mechanical properties. The results show that, as the number of loading cycles increases, residual elongation decreases, with three distinct phases of decline—slow change, gradual decline, and rapid deterioration—depending on the stress levels. SEM analysis identified damage mechanisms such as “dewetting” and particle fragmentation at the mesostructural level, which compromise the material’s structural integrity, leading to reduced residual elongation. A novel aspect of this study is the application of Williams–Landel–Ferry (WLF) theory to construct a master curve describing residual elongation decay. This approach enabled the development of a generalized model to predict the material’s degradation under fatigue loading, with experimental validation of the fitted evolution model, offering a new and effective method for assessing the long-term performance of HTPB propellants.