Mounting evidence exists that mobile voluntary counselling and testing (VCT) is able to extend coverage to new localities and populations. We describe two feasibility and acceptability pilot studies conducted in rural and urban South Africa in preparation for the larger NIMH Project Accept HIV prevention trial. A total of 1,015 individuals participated in the pilot studies. Participants in rural Vulindlela were younger (median 22 years) compared to urban Soweto (p < 0.001). Young people were more likely to be first time testers in both sites (p = 0.01 in Vulindlela, p < 0.001 in Soweto), with significantly more men likely to be first time testers than women (p = 0.01 in Vulindlela, p < 0.001 in Soweto). User satisfaction with mobile VCT was extremely high in both sites. Our study shows that providing mobile, high-quality and easy to access services in a high prevalence context is a feasible way to engage youth, men and more rural populations in HIV counselling and testing.