BACKGROUND: The basic reproduction number, [Formula: see text], is one of the many measures of the epidemic potential of an infection in a population. We estimate HIV [Formula: see text] over 18 years in a rural population in Uganda, examine method-specific differences in estimated [Formula: see text], and estimate behavioural changes that would reduce [Formula: see text] below one. METHODS: Data on HIV natural history and infectiousness were collated from literature. Data on new sexual partner count were available from a rural clinical cohort in Uganda over 1991-2008. [Formula: see text] was estimated using six methods. Behavioural changes required to reduce [Formula: see text] below one were calculated. RESULTS: Reported number of new partners per year was 0 to 16 (women) and 0 to 80 (men). When proportionate sexual mixing was assumed, the different methods yielded comparable [Formula: see text] estimates. Assuming totally assortative mixing led to increased [Formula: see text] estimates in the high sexual activity class while all estimates in the low-activity class were below one. Using the "effective" partner change rate introduced by Anderson and colleagues resulted in [Formula: see text] estimates all above one except in the lowest sexual activity class. [Formula: see text] could be reduced below one if: (a) medium risk individuals reduce their partner acquisition rate by 70% and higher risk individuals reduce their partner acquisition rate by 93%, or (b) higher risk individuals reduce the partner acquisition rate by 95%. CONCLUSIONS: The estimated [Formula: see text] depended strongly on the method used. Ignoring variation in sexual activity leads to an underestimation of [Formula: see text]. Relying on behaviour change alone to eradicate HIV may require unrealistically large reductions in risk behaviour, even though for a small proportion of the population. To control HIV, complementary prevention strategies such as male circumcision and HIV treatment services need rapid scale up.