Creep-fatigue interaction occurs in many structural components of high-temperature systems operating under cyclic and steady-state service conditions, such as in nuclear power plants, aerospace, naval, and other industrial applications. Thus, understanding micromechanisms governing high-temperature creep-fatigue behavior is essential for safety and design considerations. In this work, stress-controlled creep-fatigue tests of advanced austenitic stainless steel (Alloy 709) were performed at a 400 MPa stress range and 750 °C with tensile hold times of 0, 60, 600, 1800, and 3600 s, followed by microstructural examinations. The creep-fatigue lifetime of the Alloy 709 was found to decrease with increasing hold time until reaching a saturation level where the number of cycles to failure did not exhibit a significant decrease. Softening behavior was observed at the beginning of the test, possibly due to the recovery of entangled dislocations and de-twining. In addition, hysteresis loops showed ratcheting behavior, although the mean stress was zero during creep-fatigue cycling, which was attributed to activity of partial dislocations. Microstructural examination of the fracture surfaces showed that fatigue failure dominated at small hold times where the cracks initiated at the surface of the sample. Larger creep cracks were found for longer hold times with a lower probability of dimpled cavities, indicating the dominance of creep deformation. The results were compared with other commonly used stainless steels, and plausible reasons for the observed responses were described.