BACKGROUND: The CDC recommends routine voluntary HIV testing of all patients 13-64 years of age. Despite this recommendation, HIV testing rates are low even among those at identifiable risk, and many patients do not return to receive their results. OBJECTIVE: To examine the costs and benefits of strategies to improve HIV testing and receipt of results. DESIGN: Cost-effectiveness analysis based on a Markov model. Acceptance of testing, return rates, and related costs were derived from a randomized trial of 251 patients; long-term costs and health outcomes were derived from the literature. SETTING/TARGET POPULATION: Primary-care patients with unknown HIV status. INTERVENTIONS: Comparison of three intervention models for HIV counseling and testing: Model A = traditional HIV counseling and testing; Model B = nurse-initiated routine screening with traditional HIV testing and counseling; Model C = nurse-initiated routine screening with rapid HIV testing and streamlined counseling. MAIN MEASURES: Life-years, quality-adjusted life-years (QALYs), costs and incremental cost-effectiveness. KEY RESULTS: Without consideration of the benefit from reduced HIV transmission, Model A resulted in per-patient lifetime discounted costs of $48,650 and benefits of 16.271 QALYs. Model B increased lifetime costs by $53 and benefits by 0.0013 QALYs (corresponding to 0.48 quality-adjusted life days). Model C cost $66 more than Model A with an increase of 0.0018 QALYs (0.66 quality-adjusted life days) and an incremental cost-effectiveness of $36,390/QALY. When we included the benefit from reduced HIV transmission, Model C cost $10,660/QALY relative to Model A. The cost-effectiveness of Model C was robust in sensitivity analyses. CONCLUSIONS: In a primary-care population, nurse-initiated routine screening with rapid HIV testing and streamlined counseling increased rates of testing and receipt of test results and was cost-effective compared with traditional HIV testing strategies.