Using data from Botswana’s largest HIV testing and counseling (HTC) provider, Tebelopele, we evaluate populations served and gender-specific correlates of testing HIV-positive among clients of two programs: standalone centers and outreach testing. Client records from January to June 2007 (n = 47,890) were evaluated by HTC program and gender. Bivariate and multivariate analyses were performed to identify demographic, testing, and risk-behavior variables associated with testing HIV-positive. Compared to outreach testing, standalone centers served proportionally more clients who were young, well-educated, unmarried, and HIV-infected; outreach testing reached an older, less-educated population. Age, educational attainment, marital status, couples testing, testing because of illness or discordant relationship, and nonuse of condoms (among young clients only) were consistently associated with testing HIV-positive, by HTC program and gender. Our evaluation suggests that Tebelopele standalone and outreach HTC programs serve different populations, and identifies strategies to reduce HIV infection risk and to improve uptake of HTC by HIV-infected, undiagnosed Batswana.