Sexual behavior change to reduce the risk of HIV infection is a dynamic multi-staged process. We present an empirical model for change, where we describe a stage of initiation of safer sexual practices, followed by a consolidation stage, and a long-term maintenance stage. The process of change can be interrupted by occasional or repeated lapses. We apply this multi-stage model to sexual behavior in a cohort of gay men from the Chicago area. The prevalence of various stages are reported between 1986 and 1991. Men infected with HIV tended to initiate change to safer sex later than those who were not, but maintained change or relapsed to unsafe practices in the same proportion. Implications regarding factors associated with relapse to unsafe sex, and interventions to prevent relapse, are discussed