Background A key conclusion of the Four Cities Study, carried out to explore reasons for heterogeneity in the HIV epidemic between two cities in sub-Saharan Africa with relatively low prevalence (Cotonou and Yaounde) and two with high prevalence (Kisumu and Ndola), was that differences in biological cofactors outweighed differences in sexual risk behaviours. The authors explore an alternative hypothesis, that risk behaviours were historically higher in the high-prevalence cities. They also investigate the effects of different prevalence of male circumcision on the HIV epidemics in the four cities. Methods A transmission model was fitted to data from the Four Cities Study. Default scenarios included biological cofactor effects on HIV transmission. Counter-factual scenarios were simulated without biological cofactors, with and without higher historical sexual behaviours, and with various rates of male circumcision. Results Simulated adult HIV prevalence in 1997 for the default scenarios was 3.1%, 7.8%, 28.9% and 27.1% in Cotonou, Yaounde, Kisumu and Ndola, respectively, in line with data. Without biological cofactors, even implausibly high historical levels of risk behaviour in East Africa could not reproduce the observed heterogeneity in the late 1990s. Increasing the proportion of men circumcised in Ndola from 10% to 100% reduced HIV prevalence in 1997 to 7%. Decreasing the proportion circumcised in Yaounde from 100% to 10% increased HIV prevalence to 26%. Conclusions Differences in male circumcision rates are likely to have played a key role in the heterogeneous spread of HIV across Africa. The effect of circumcision interventions can vary depending on the epidemic setting, with a larger effect in more generalised epidemics.