Evidence has linked residential instability and engagement in high-risk behaviors. This paper longitudinally examines the relationship between changes in residential stability and changes in HIV risk behaviors among Montréal street youth (SY). Between April 2006 and May 2007, 419 SY (18-25 years old) were recruited in a cohort study. SY (using Montréal street youth agencies services) were eligible if they had had at least one 24-hour episode of homelessness in the previous 30 days. Baseline and follow-up interviews, carried out every 3 months, included completion of a questionnaire (based on Life History Calendar Technique) assessing daily sleeping arrangements since the last interview, and monthly sexual and drug use behaviors. Using mixed-effects logistic regression method, we examined the association between various risk behaviors and residential stability, reached when a youth resided in any of the following settings for a whole month: own place; friends'/partner's/parent's place; any types of housing service (excluding emergency shelters). Analyses were carried out controlling for gender, age, education level, lifetime duration of homelessness, childhood sexual trauma, and lifetime mental health disorders. As of January 2009, 360 SY (79% boys) had completed at least one follow-up interview, representing 4,889 months of follow-up. Residential stability was significantly associated with the following: sex exchange (adjusted odd ratio [AOR], 0.25; 95% confidence interval [CI], 0.14-0.37), drug injection (AOR, 0.55; CI, 0.33-0.76), daily alcohol consumption (AOR, 0.58; CI, 0.42-0.74), polydrug consumption (AOR, 0.61; CI, 0.50-0.73), polydrug consumption excluding marijuana (AOR, 0.55; CI, 0.45-0.65), and multiple sex partners (=3 partners; AOR, 0.57; CI, 0.40-0.74). Our results suggest a reciprocal relationship between residential instability and HIV risk behaviors. This calls for more integrated services combining both individual and structural-level interventions to improve the health of street youth.