Abstract Background The most severe HIV epidemics worldwide occur in Lesotho, Botswana and Swaziland. Here we focus on the Lesotho epidemic, which has received little attention. We determined the within-country heterogeneity in the severity of the epidemic, and identified the risk factors for HIV infection. We also determined whether circumcised men in Lesotho have had a decreased risk of HIV infection in comparison with uncircumcised men. We discuss the implications of our results for expanding treatment (current coverage is only 60%) and reducing transmission. Methods We used data from the 2009 Lesotho Demographic and Health Survey, a nationally representative survey of 3,849 women and 3,075 men in 9,391 households. We performed multivariate analysis to identify factors associated with HIV infection in the sexually active population and calculated age-adjusted odds ratios (aORs). We constructed cartographic country-level prevalence maps using geo-referenced data. Results HIV is hyperendemic in the general population. The average prevalence is 27% in women and 18% in men, but shows substantial geographic variation. Throughout the country prevalence is higher in urban centers (31% in women; 21% in men) than in rural areas (25% in women; 17% in men), but the vast majority of HIV-infected individuals live in rural areas. Notably, prevalence is extremely high in women (18%) and men (12%) with only one lifetime sex partner. Women with more partners have a greater risk of infection: aOR 2.3 (2 to 4 partners), aOR 4.4 (≥5 partners). A less substantial effect was found for men: aOR 1.4 (3 to 6 partners), aOR 1.8 (≥7 partner). Medical circumcision protected against infection (aOR 0.5), traditional circumcision did not (aOR 0.9). Less than 5% of men in Lesotho have been medically circumcised; approximately 50% have been circumcised using traditional methods. Conclusions There is a substantial need for treatment throughout Lesotho, particularly in rural areas where there is the greatest burden of disease. Interventions aimed at reducing the number of sex partners may only have a limited effect on reducing transmission. Substantially increasing levels of medical circumcision could be very effective in reducing transmission, but will be very difficult to achieve given the current high prevalence of traditional circumcision.