Background eHealth interventions based on risk stratification have not been extensively applied for HIV behavioral interventions among HIV-negative men who have sex with men (MSM). Objective This study aimed to evaluate the efficacy of a mobile phone intervention based on an HIV risk prediction tool in promoting HIV testing and reducing high-risk behavior among HIV-negative MSM in China. Methods We performed a mobile phone–based randomized controlled clinical trial for 12 weeks. A comprehensive intervention package deployed on Jinshuju—an online survey platform—was developed and consisted of 4 components: (1) a validated HIV risk prediction tool that provides information on personalized risk reduction interventions; (2) a map of individualized HIV testing facilities based on their geographic location; (3) a QR code for free resources on HIV prevention, including condoms and HIV self-testing kits; and (4) general resources for HIV health education. MSM participants recruited from WeChat/QQ groups were randomly assigned to the intervention or control group at a 1:1 ratio. The staff sent the QR code for the comprehensive intervention package to MSM in the intervention group over WeChat and sent the QR code only for the resources on HIV health education to those in the control group. At baseline and 12-week follow-up, data on HIV-related risk behavior and HIV testing behavior were collected through the Jinshuju online survey platform. Results In total, 192 MSM were recruited and assigned to the intervention or control group (n=96 each). At week 12, the total clinical trial retention rate was 87.5%. The number of male sexual partners of the MSM in the past 3 months was significantly lower in the intervention group than in the control group (3.51, SD 4.1 vs 6.01, SD 11.4, respectively; mean difference −2.5; 95% CI −5.12 to 0.12; P=.05); the rate of condom use with casual sexual partners was higher in the intervention group than in the control group (87%, n=66/76 vs 70%, n=54/77 respectively; odds ratio 2.81, 95% CI 1.23-6.39; P=.01). The proportion of individuals intending to undergo HIV testing after in the following 30 days was marginally higher in the intervention group than in the control group (90%, n=77/86 vs 79%, n=65/82 respectively; odds ratio 2.20, 95% CI 0.90-5.35; P=.07). The incremental cost-effectiveness ratio of eHealth intervention was US $131.60 on reducing 1 sexual partner and US $19.70 for a 1% increment in condom usage with casual partners. Conclusions A comprehensive intervention based on an HIV risk prediction tool can reduce the number of male sexual partners among MSM and increase the rate of condom use with casual partners. Hence, this intervention is a very promising preventive strategy for HIV among MSM, especially in areas with a prominent HIV epidemic. Trial Registration Chinese Clinical Trial Registry ChiCTR1800017268; http://www.chictr.org.cn/showprojen.aspx?proj=29271