Background The use of mobile communication technologies (mHealth: mobile health) in chronic disease management has grown significantly over the years. mHealth interventions have the potential to decentralize access to health care and make it convenient, particularly in resource-constrained settings. It is against this backdrop that we aimed to codevelop (with potential users) a new generation of mobile phone–connected HIV diagnostic tests and Web-based clinical care pathways needed for optimal delivery of decentralized HIV testing, prevention, and care in low- and middle-income countries. Objective The aim of this study was to understand ways in which an mHealth intervention could be developed to overcome barriers to existing HIV testing and care services and promote HIV self-testing and linkage to prevention and care in a poor, HIV hyperendemic community in rural KwaZulu-Natal, South Africa. Methods A total of 54 in-depth interviews and 9 focus group discussions were conducted with potential users (including health care providers) in 2 different communities. Theoretically informed by the candidacy framework, themes were identified from the interview transcripts, manually coded, and thematically analyzed. Results Participants reported barriers, such as fear of HIV identity, stigma, long waiting hours, clinic space, and health care workers’ attitudes, as major impediments to effective uptake of HIV testing and care services. People continued to reassess their candidacy for HIV testing and care services on the basis of their experiences and how they or others were treated within the health systems. Despite the few concerns raised about new technology, mobile phone–linked HIV testing was broadly acceptable to potential users (particularly men and young people) and providers because of its privacy (individual control of HIV testing over health provider–initiated testing), convenience (individual time and place of choice for HIV testing versus clinic-based testing), and time saving. Conclusions Mobile phone–connected HIV testing and Web-based clinical care and prevention pathways have the potential to support access to HIV prevention and care, particularly for young people and men. Although mHealth provides a way for individuals to test their candidacy for HIV services, the barriers that can make the service unattractive at the clinic level will also need to be addressed if potential demand is to turn into actual demand.