A new mHealth service, Clinic Finder, was designed to provide a location-based service for any cellphone user in South Africa dialing a dedicated USSD string to find the nearest public primary health care facility. The service was funded by a European Union grant to Cell-Life to support the National Department of Health. Clinic Finder's aims were to provide a reliable and accurate service, and to assess both the most effective means of advertising the service as well as interest in the service. Users dialing the USSD string are asked to agree to geo-location (Vodacom and MTN users) or asked to enter their province, town and street (virtual network users and those choosing not to geo-locate). The service provider, AAT, sends the data to Cell-Life where an SMS with details of the nearest public primary health care facility is sent to the user by Cell-Life's open-source Communicate platform. The service was advertised on 3 days in 2014 using two different means: a newspaper ad on 20 May 2014 and Please Call Me ads on 30 July 2014 and 14 August 2014. 28.2% of unique users on 20 May 2014, 10.5% of unique users on 30 July 2014 and 92.8% of unique users on 14 August 2014 who agreed to geo-location successfully received SMSs. However, only 4.2%, 0.5%, and 2.4% of unique users responding to each advertisement who did not geo-locate then received an SMS. A small survey of users following the 20 May 2014 newspaper ad found overall interest in the idea of Clinic Finder, though unsuccessful users were more likely to dislike the service. The overall experience of using location based services and USSD for Clinic Finder suggests a need in the field of mHealth for wider availability of data on service usability and effectiveness.