Stages of change measure an individual's readiness to alter a health behavior. This study examined the latent longitudinal patterns of stages of change (SoC) for regular exercise over time among individuals participating in a lifestyle intervention project. It also investigated the association between the longitudinal patterns of SoC and intervention outcomes using a new statistical method to assess the relationship between latent class membership and distal outcomes. We analyzed data from the Special Diabetes Program for Indians Diabetes Prevention Program, a lifestyle intervention program to prevent diabetes among American Indians and Alaska Natives. Latent class analysis (LCA) was conducted to identify the longitudinal patterns of SoC for regular exercise reported at three time points. LCA with distal outcomes was performed to investigate the associations between latent class membership and behavioral changes after the intervention. The parameters and standard errors of the LCA with distal outcomes models were estimated using an improved three-step approach. Three latent classes were identified: Pre-action, Transition, and Maintenance classes. The Transition class, where stage progression occurred, had the greatest improvements in physical activity and weight outcomes at both time points post-baseline among female participants. It also had the largest improvements in weight outcomes among male participants. Furthermore, the Pre-action class had more attenuation in the improvements they had achieved initially than the other two classes. These findings suggest the potential importance of motivating participants to modify their readiness for behavioral change in future lifestyle interventions.