Ecological comparisons in sub-Saharan Africa show that HIV prevalence is lower where men are generally circumcised than where they are not. Randomized controlled trials have found a 50-60 reduction in HIV acquisition for newly circumcised men. Yet in Malawi, HIV prevalence is highest in several districts in the Southern Region, where men are commonly circumcised. We draw upon a population-based sample of ever-married women to explore this unexpected finding. Our data show that in the southern district of Balaka, women with circumcised spouses have a lower probability of HIV infection compared to those with uncircumcised spouses. However, the strength of this effect is conditioned by specific marital histories: among women with circumcised spouses, those with multiple marriages and an absence of spousal co-residence have a higher probability of HIV infection than do those married once and those who have never lived apart from their spouses. The history of marital turnover and female-headed households among the ethnic groups of Balaka offer insight into the district's elevated HIV levels.