Sub-Saharan Africa has a high rate of HIV infection, most of which is attributable to heterosexual transmission. Few attempts have been made to assess the extent of HIV transmission within marriages, and HIV-prevention efforts remain focused on abstinence and non-marital sex. We aimed to estimate the proportion of heterosexual transmission of HIV which occurs within married or cohabiting couples in urban Zambia and Rwanda each year. We used population-based data from Demographic and Health Surveys (DHS) on heterosexual behaviour in Zambia in 2001-02 and in Rwanda in 2005. We also used data on the HIV serostatus of married or cohabiting couples and non-cohabiting couples that was collected through a voluntary counselling and testing service for urban couples in Lusaka, in Zambia, and Kigali, in Rwanda. We estimated the probability that an individual would acquire an incident HIV infection from a cohabiting or non-cohabiting sexual partner, and then the proportion of total heterosexual HIV transmission which occurs within married or cohabiting couples in these settings each year. We analysed DHS data from 1739 Zambian women, 540 Zambian men, 1176 Rwandan women, and 606 Rwandan men. Under our base model, we estimated that 55.1% to 92.7% of new heterosexually acquired HIV infections among adults in urban Zambia and Rwanda occurred within serodiscordant marital or cohabiting relationships, depending on the sex of the index partner and on location. Under our extended model, which incorporated the higher rates of reported condom use that we found with non-cohabiting partners, we estimated that 60.3% to 94.2% of new heterosexually acquired infections occurred within marriage or cohabitation. We estimated that an intervention for couples which reduced transmission in serodiscordant urban cohabiting couples from 20% to 7% every year could avert 35.7% to 60.3% of heterosexually transmitted HIV infections that would otherwise occur. Since most heterosexual HIV transmission for both men and women in urban Zambia and Rwanda takes place within marriage or cohabitation, voluntary counselling and testing for couples should be promoted, as should other evidence-based interventions that target heterosexual couples.