Background: There is a pressing need to ensure that youth in high HIV prevalence settings are prepared for a safer sexual debut. Smartphone ownership is increasing dramatically in low-income and middle-income countries. Smartphone games that are appropriately grounded in behavioral theory and evidence-based practice have the potential to become valuable tools in youth HIV prevention efforts in Sub-Saharan Africa. Objective: To pilot-test a theory-based, empirically grounded smartphone game for young Kenyans designed to increase age and condom use at first sex, aiming to establish directionality of effects on behavior change. Methods: Tumaini (“hope for the future” in Swahili) is an interactive, narrative-based game grounded in social cognitive theory. A randomized controlled pilot study was conducted in Kisumu, Western Kenya, from April to June 2017 with 60 participants aged 11-14 (mean 12.7) years. Intervention arm participants (n=30) were provided with an Android smartphone with Tumaini installed on it and were instructed to play the game for at least 1 hour a day for 16 days; control arm participants (n=30) received no intervention. All participants completed a survey on behavioral mediators, delivered via an audio computer-assisted self-interview system at baseline (T1), post intervention (T2), and at 6 weeks postintervention (T3). The postintervention survey for intervention arm participants included questions eliciting feedback on the game. Intervention arm participants and their parents participated in 8 postintervention focus group discussions. Game log files were analyzed to calculate the length of exposure to the game. Behavioral survey data were analyzed using two-sample t tests to compare mean change from T1 to T2 and to T3 for intervention versus control arm participants. Descriptive statistics on game feedback questions were computed. Focus group transcripts were uploaded to MAXQDA software, where they were labeled with deductive and inductive codes. Data were analyzed thematically and compared across demographics. Results: Intervention arm participants played Tumaini for a mean of approximately 27 hours. The intervention arm showed significant gains in sexual health-related knowledge and self-efficacy (both P<.001), behavioral intention for risk-avoidance strategies and sexual risk communication (P=.006), and overall survey scores (P<.001) compared with the control arm at T3. The postintervention survey revealed high subjective measures of the game's value, relevance, and appeal. Focus groups identified a wide range of knowledge and skills the participants had gained, including setting goals and planning how to achieve them, which was perceived as a key motivator for avoiding or reducing risk. Conclusions: The study supports the need for further research to assess the efficacy of the game-based intervention. If proven efficacious, smartphone games have the potential to dramatically increase the reach of culturally adapted behavioral interventions while ensuring fidelity to intervention design.