Background: Evidence suggests that HIV prevalence amongst young Zambians has declined recently, especially in higher-education groups. We studied trends in key sexual behaviour indicators among 15–24 year-olds from 1995 to 2003, including the associations between sexual behaviour change and education. Methods: The data stem from a series of three population-based surveys conducted in 1995 (n = 1720), 1999 (n = 1946) and 2003 (n = 2637). Logistic regression and Extended Mantel Haenszel Chi Square for linear trends were used to compare the three surveys. Results: Men and lower-education groups reported more than one sexual partner in the year immediately prior to the survey more frequently than did women and higher-education groups (p < 0.01), but these proportions declined regardless of sex and residence. Substantial delays in childbearing were observed, particularly among higher-education and urban respondents. Condom use at least for casual sexual intercourse increased from 1995 to 2003; the level was highest among urban and higher-education groups. The number of women reporting frequent dry sex using traditional agents fell during the period. Participants from the rural area and those with less education reported more sexual experience than urban and higher-education participants in 2003. The reported number of sexual partners during the year immediately prior to the survey was a factor that reduced the association between HIV and survey times among sexually active young urban men and women. Conclusion: High risk behaviours clearly decreased, especially in higher-educated and urban groups, and there is a probable association here with the decline in HIV prevalence in the study population. Fewer sexual partners and condom use were among the core factors involved for both sexes; and for women a further factor was delayed child-bearing.