Background Nonattendance at vaccination appointments is a big challenge for health workers as it is difficult to track routine vaccination schedules. In Ethiopia, 3 out of 10 children have incomplete vaccination and the timely receipt of the recommended vaccines is low. Thus, innovative strategies are required to reach the last mile where mobile technology can be effectively utilized to achieve better compliance. Despite this promising technology, little is known about the role of text message–based mobile health interventions in improving the complete and timely receipt of routine childhood vaccinations in Ethiopia. Objective This trial aimed to determine the effect of mobile phone text message reminders on the completion and timely receipt of routine childhood vaccinations in northwest Ethiopia. Methods A two-arm, parallel, superiority randomized controlled trial was conducted in 9 health facilities in northwest Ethiopia. A sample size of 434 mother-infant pairs was considered in this trial. Randomization was applied in selected health facilities during enrollment with a 1:1 allocation ratio by using sealed and opaque envelopes. Participants assigned to the intervention group received mobile phone text message reminders one day before the scheduled vaccination visits. Owing to the nature of the intervention, blinding of participants was not possible. Primary outcomes of full and timely completion of vaccinations were measured objectively at 12 months. A two-sample test of proportion and log-binomial regression analyses were used to compare the outcomes between the study groups. A modified intention-to-treat analysis approach was applied and a one-tailed test was reported, considering the superiority design of the trial. Results A total of 426 participants were included for the analysis. We found that a higher proportion of infants in the intervention group received Penta-3 (204/213, 95.8% vs 185/213, 86.9%, respectively; P<.001), measles (195/213, 91.5% vs 169/213, 79.3%, respectively; P<.001), and full vaccination (176/213, 82.6% vs 151/213, 70.9%, respectively; P=.002; risk ratio 1.17, 95% lower CI 1.07) compared to infants in the usual care group. Similarly, a higher proportion of infants in the intervention group received Penta-3 (181/204, 88.7% vs 128/185, 69.2%, respectively; P<.001), measles (170/195, 87.1% vs 116/169, 68.6%, respectively; P<.001), and all scheduled vaccinations (135/213, 63.3% vs 85/213, 39.9%, respectively; P<.001; risk ratio 1.59, 95% lower CI 1.35) on time compared to infants in the usual care group. Of the automatically sent 852 mobile phone text messages, 764 (89.7%) were delivered successfully to the participants. Conclusions Mobile phone text message reminders significantly improved complete and timely receipt of all recommended vaccines. Besides, they had a significant effect in improving the timely receipt of specific vaccines. Thus, text message reminders can be used to supplement the routine immunization program in resource-limited settings. Considering different contexts, studies on the implementation challenges of mobile health interventions are recommended. Trial Registration Pan African Clinical Trial Registry PACTR201901533237287; https://pactr.samrc.ac.za/TrialDisplay.aspx?TrialID=5839