Background HIV voluntary counseling and testing (VCT) is promoted to increase serostatus awareness and entry into care and treatment. However, in Africa there is little guidance on whether and how often repeat testing should be done for those who test negative. Tanzanian VCT guidelines recommend a single repeat test after 3 months, a policy suited to the concept of a single exposure. In order to inform allocation of VCT resources, we evaluated the cost-effectiveness of alternative repeat testing strategies under various HIV incidence scenarios. Methods 20-year survival, HIV treatment costs, and cost of VCT were modeled for 3 hypothetical cohorts of 10,000 persons each with HIV incidence rates of 0.1% (low), 0.5% (medium), and 2.0% (high) respectively. Estimates of CD4-count decline, treatment failure, mortality, and cost with and without treatment from Tanzania were used. Marginal costs per case identified were compared to first-time testing in a previously untested population. Costs and benefits were discounted at 3% per year. Results Under current Tanzania VCT guidelines with repeat testing after 3 months the cost per case identified from repeat testing ranges from US$3,908 to $28,666 in high and low incidence populations, respectively. Changing the repeat testing interval to 1 year reduces the cost per case to $2,914 at high and $8,887 at low incidence. An interval of 5 years reduces cost per case to as low as $2,500 in the high incidence population. Conclusions While beneficial relative to one-time testing, the Tanzania strategy of a single repeat test after 3 months is costly, particularly in low-incidence populations. At the population level repeat testing at longer intervals is more cost effective. An extension of repeat testing intervals in low incidence populations results in the greatest absolute reduction in cost per case identified. We suggest that testing policies in countries with generalized epidemics should advocate not only for universal testing, but also for regular repeat testing. Our data demonstrate benefits of tailoring testing intervals to local prevalence and incidence, and resource constraints in various populations.