Background: In 2010, the human papillomavirus (HPV) vaccination was introduced in the Dutch National Immunization Program for 12-year-old girls, aiming to reduce the incidence of cervical cancer in women. HPV vaccination uptake turned out to be lower than expected: 61% versus 70%, respectively. Mothers were shown to play the most important role in the immunization decision about this vaccination. They had also expressed their need for interactive personal information about the HPV vaccination over and above the existing universal general information. To improve the effectiveness of the existing education about the HPV vaccination, we systematically developed a Web-based tailored intervention with virtual assistants providing mothers of girls to be invited with tailored feedback on their decision making about the HPV vaccination. Objective: The aim of this study was to evaluate the effectiveness of the Web-based tailored intervention for promoting HPV vaccination acceptance by means of a randomized controlled trial (RCT). Methods: Mothers were recruited via the Dutch vaccination register (Praeventis) (n=36,000) and three Web-based panels (n=2483). Those who gave informed consent (N=8062) were randomly assigned to the control (n=4067) or intervention condition (n=3995). HPV vaccination uptake, as registered by Praeventis once the HPV vaccination round was completed, was used as the primary outcome. Secondary outcomes were differential scores across conditions between baseline (before the provided access to the new tailored intervention) and follow-up (just before the first vaccination) regarding the mothers' degree of informed decision making (IDM), decisional conflict, and critical determinants of HPV vaccination uptake among which are intention, attitude, risk perception, and outcome beliefs. Results: Intention-to-treat analysis (N=8062) showed a significant positive effect of the intervention on IDM, decisional conflict, and nearly all determinants of HPV vaccination uptake (P < .001). No effect was found on uptake (P=.60). This may be attributed to the overall high uptake rates in both conditions. Mothers evaluated the intervention as highly positive, including the website as well as the virtual assistants that were used to deliver the tailored feedback. Conclusions: This computer-tailored intervention has the potential to improve HPV vaccination acceptability and IDM and to decrease decisional conflict among mothers of invited girls. Implications for future research are discussed.