BACKGROUND: Across sub-Saharan Africa, men's levels of HIV-testing remain inadequate relative to women's. Men are less likely to access anti-retroviral therapy and experience higher levels of morbidity and mortality once initiated on treatment. More frequent HIV-testing by men at continued risk of HIV-infection is required to facilitate earlier diagnosis. This study explored the frequency of HIV-testing among a rural population of men and the factors associated with more frequent HIV-testing. METHODS: We conducted a secondary analysis of a population-based survey in three rural district in Zambia, from February-November, 2013. Households (N = 300) in randomly selected squares from 42 study sites, defined as a health facility and its catchment area, were invited to participate. Individuals in eligible households were invited to complete questionnaires regarding demographics and HIV-testing behaviours. Men were defined as multiple HIV-testers if they reported more than one lifetime test. Upon questionnaire completion, individuals were offered rapid home-based HIV-testing. RESULTS: Of the 2376 men, more than half (61%) reported having ever-tested for HIV. The median number of lifetime tests was 2 (interquartile range = 1-3). Just over half (n = 834; 57%) of ever-testers were defined as multiple-testers. Relative to never-testers, multiple-testers had higher levels of education and were more likely to report an occupation. Among the 719 men linked to a spouse, multiple-testing was higher among men whose spouse reported ever-testing (adjusted prevalence ratio = 3.02 95% CI: 1.37-4.66). Multiple-testing was higher in study sites where anti-retroviral therapy was available at the health facility on the day of a health facility audit. Among ever-testers, education and occupation were positively associated with multiple-testing relative to reporting one lifetime HIV-test. Almost half (49%) of ever-testers accepted the offer of home-based HIV-testing. DISCUSSION: Reported HIV-testing increased among this population of men since a 2011/12 survey. Yet, only 35% of all men reported multiple lifetime HIV-tests. The factors associated with multiple HIV-testing were similar to factors associated with ever-testing for HIV. Men living with HIV were less likely to report multiple HIV-tests and employment and education were associated with multiple-testing. The offer of home-based HIV-testing increased the frequency of HIV-testing among men. CONCLUSION: Although men's levels of ever-testing for HIV have increased, strategies need to increase the lifetime frequency of HIV-testing among men at continued risk of HIV-infection.