OBJECTIVES: To investigate the relative effectiveness of different HIV testing and counselling (HTC) services in improving HIV diagnosis rates and increasing HTC coverage in African settings. METHODS: Patient records from three HTC services [community outreach HTC during cohort study rounds (CO-HTC), walk-in HTC at the local health centre (WI-HTC) and antenatal HIV testing (ANC-HTC)] were linked to records from a community cohort study using a probabilistic record linkage algorithm. Characteristics of linked users of each HTC service were compared to those of cohort participants who did not use the HTC service using logistic regression. Data from three cohort study rounds between 2003 and 2010 were used to assess trends in the proportion of persons testing at different service types. RESULTS: The adjusted odds ratios for HTC use among men with increasing numbers of sexual partners in the past year, and among HIV-positive men and women compared to HIV-negative men and women, were higher at WI-HTC than at CO-HTC and ANC-HTC. Among sero-survey participants, the largest numbers of HIV-positive men and women learned their status via CO-HTC. However, we are likely to have underestimated the numbers diagnosed at WI-HTC and ANC-HTC, due to low sensitivity of the probabilistic record linkage algorithm. CONCLUSIONS: Compared to CO-HTC or ANC-HTC, WI-HTC was most likely to attract HIV-positive men and women, and to attract men with greater numbers of sexual partners. Further research should aim to optimise probabilistic record linkage techniques, and to investigate which types of HTC services most effectively link HIV-positive people to treatment services relative to the total cost per diagnosis made.