The objective of this study is to describe HIV-testing among men in rural Lusaka Province, Zambia, using a population-based survey for a cluster-randomized trial. Households (N = 120) were randomly selected from each of the 42 clusters, defined as a health facility catchment area. Individuals aged 15-60 years were invited to complete questionnaires regarding demographics and HIV-testing history. Men testing in the last year were defined as recent-testers. After questionnaire completion adults were offered home-based rapid HIV-testing. Of the 2,828 men, 53 % reported ever-testing and 25 % recently-testing. Factors independently associated with ever- and recent-testing included age 20+ years, secondary/higher education, being married or widowed, a history of TB-treatment and higher socioeconomic position. 53 % of never-testers and 57 % of men who did not report a recent-test accepted home-based HIV-testing. Current HIV-testing approaches are inadequate in this high prevalence setting. Alternative strategies, including self-testing, mobile- or workplace-testing, may be required to complement facility-based services.