The application of structural health monitoring (SHM) in composite airframe structural elements under long-term realistic fatigue loading needs to consider the structural behavior on the global level, which is an intricate task. The overall structural stiffness is a key design parameter for composite structures and the stiffness degradation under fatigue loading is closely related to the damage accumulation and failure mechanism which can be used as an indicator for the structural degradation. Therefore, this paper investigates the use of guided waves in axial stiffness degradation estimation for stiffened carbon fiber reinforced polymer (CFRP) composite panels under post-buckling compression-compression (C-C) fatigue loads. Impacted or artificially debonded stiffened composite panels are tested under fatigue until failure and guided waves are acquired using a network of piezoelectric (PZT) sensors at fixed cycle intervals. The guided wave phase velocity along the loading direction is extracted to estimate the axial stiffness degradation with the consideration of mode conversion and failure of PZT sensors. The estimated stiffness of five stiffened composite panels matches well with the stiffness calculated from the load–displacement curves. The estimated stiffness is also assessed using prognostic performance metrics and shows good potential for being used as a health indicator for prognostic purposes.