To diagnose ≥90% HIV-infected residents (diagnostic coverage), the Bukoba Combination Prevention Evaluation (BCPE) implemented provider-initiated (PITC), home- (HBHTC), and venue-based (VBHTC) HIV testing and counseling (HTC) intervention in Bukoba Municipal Council, a mixed urban and rural lake zone community of 150,000 residents in Tanzania. This paper describes the methods, outcomes, and incremental costs of these HTC interventions. PITC was implemented in outpatient department clinics in all eight public and three faith-based health facilities. In clinics, lay counselors routinely screened and referred eligible patients for HIV testing conducted by HTC-dedicated healthcare workers. In all 14 wards, community teams offered HTC to eligible persons encountered at 31,293 home visits and at 79 male- and youth-frequented venues. HTC was recommended for persons who were not in HIV care or had not tested in the prior 90 days. BCPE conducted 133,695 HIV tests during the 2.5 year intervention (PITC: 88,813, 66%; HBHTC: 27,407, 21%; VBHTC: 17,475, 13%). Compared with other strategies, PITC conducted proportionally more tests among females (65%), and VBHTC conducted proportionally more tests among males (69%) and young-adults aged 15-24 years (42%). Of 5,550 (4.2% of all tests) HIV-positive tests, 4,143 (75%) clients were newly HIV diagnosed, including 1,583 males and 881 young adults aged 15-24 years. Of HIV tests conducted 3.7%, 1.8%, and 2.1% of PITC, HBHTC, and VBHTC clients, respectively, were newly HIV diagnosed; PITC accounted for 79% of all new diagnoses. Cost per test (per new diagnosis) was $4.55 ($123.66), $6.45 ($354.44), and $7.98 ($372.67) for PITC, HBHTC, and VBHTC, respectively. In a task-shifting analysis in which lay counselors replaced healthcare workers, estimated costs per test (per new diagnosis) would have been $3.06 ($83.15), $ 4.81 ($264.04), and $5.45 ($254.52), for PITC, HBHTC, and VBHTC, respectively. BCPE models reached different target groups, including men and young adults, two groups with consistently low coverage. Implementation of multiple models is likely necessary to achieve ≥90% diagnostic coverage.