BACKGROUND: Sexual behavioural change is essential to prevent HIV infections in Africa and statistical analysis of risk factors at the individual-level may be used to design interventions. The importance of reducing cross-generational sex (young women having sex with older men) and delaying age at first sex on the spread of HIV at the population-level has been presumed but not scientifically investigated and quantified. METHODS: A mathematical model of heterosexual spread of HIV was developed to predict the population-level impact of reducing cross-generational sex and delaying sexual debut. RESULTS: The impact of behaviour change on the spread of HIV is sensitive to the structure and reaction of the sexual network. Reducing cross-generational sex could have little impact on the risk of infection unless it is accompanied by a reduction in the number of risky sexual contacts. Even peer-to-peer sexual mixing can support high endemic levels of HIV. The benefit of delaying sexual debut is comparatively small and is reduced if males continue to prefer young partners or if young women spend more time unmarried. In Manicaland, Zimbabwe, if older men were to use condoms as frequently as young men, the reduction in risk of infection could exceed that generated by a two-year delay in first sex. CONCLUSIONS: At the individual-level avoiding sex with older partners and delaying sexual debut can decrease the risk of infection but at the population-level these interventions may do little to limit the spread of HIV without wider-ranging behavioural changes throughout the sexual network.