Background HealthMindr is a mobile phone HIV prevention app for men who have sex with men (MSM). In a previous pilot study, HealthMindr was found to be acceptable among users and to demonstrate preliminary effectiveness for increasing pre-exposure prophylaxis (PrEP) uptake among MSM. PrEP is a highly effective HIV prevention intervention; however, uptake remains low. Objective To assess the efficacy of a mobile app for increasing PrEP uptake among MSM in the southern United States. Methods In this randomized controlled trial, we will assess the efficacy of HealthMindr for increasing PrEP uptake among MSM in the following three southern US cities: Atlanta, Georgia; Jackson, Mississippi; and Washington, DC. In total, 657 men will be recruited and randomized to intervention and control arms in a 2:1 ratio. Participants in the intervention arm will receive access to the full HealthMindr app, with information and resources about PrEP (eg, frequently asked questions, risk assessment tool, and PrEP provider locator), other HIV prevention information, ability to order free HIV/sexually transmitted infection test kits, and additional resources related to substance use and mental health. Participants in the control arm will use the HealthMindr app but will only have access to the study timeline and a message center to communicate with study staff. Participants will complete quarterly surveys to assess self-reported PrEP uptake over 12 months of follow-up. Self-reported PrEP uptake will be verified by dried blood spot testing and/or uploading a photograph of a PrEP prescription. Results Participant recruitment is expected to begin in January 2020. Conclusions This trial will determine whether the HealthMindr app can increase PrEP uptake among MSM in the southern United States. Trial Registration ClinicalTrials.gov NCT03763942; https://clinicaltrials.gov/ct2/show/NCT03763942 International Registered Report Identifier (IRRID) PRR1-10.2196/16231