We estimated the effectiveness and cost-effectiveness of changes in concurrent sexual partnerships in reducing the spread of HIV in sub-Saharan Africa. Using data from Swaziland, Tanzania, Uganda and Zambia, we estimated country-specific concurrency behaviour from sexual behaviour survey data on the number of partners in the past 12 months, and we developed a network model to compare the impact of three behaviour changes on the HIV epidemic: (1) changes in concurrent partnership patterns to strict monogamy; (2) partnership reduction among those with the greatest number of partners; and (3) partnership reduction among all individuals. We estimated the number of new HIV infections over 10 years and the cost per infection averted. Given our assumptions and model structure, we find that reducing concurrency among high-risk individuals averts the most infections and increasing monogamy the least (11.7% versus 8.7% reduction in new infections, on average, for a 10% reduction in concurrent partnerships). A campaign that costs US$1 per person annually is likely cost-saving if it reduces concurrency by 9% on average, given our baseline estimates of concurrency. In sensitivity analysis, the rank ordering of behaviour change scenarios was unaffected by potential over-estimation of concurrency, though the number of infections averted decreased and the cost per HIV infection averted increased. Concurrency reduction programmes may be effective and cost-effective in reducing HIV incidence in sub-Saharan Africa if they can achieve even modest impacts at similar costs to past mass media campaigns in the region. Reduced concurrency among high-risk individuals appears to be most effective in reducing HIV incidence, but concurrency reduction in other risk groups may yield nearly as much benefit.