Background In the Netherlands, since 1996, a national cervical cancer (CC) screening program has been implemented for women aged 30 to 60 years. Regional screening organizations send an invitation letter and information brochure in Dutch to the home addresses of targeted women every 5 years. Although this screening is free of charge, Turkish- and Moroccan-Dutch women, especially, show low screening participation and limited informed decision-making (IDM). As Turkish- and Moroccan-Dutch women indicated their need for information on the practical, emotional, cultural, and religious aspects of CC screening, we developed a culturally sensitive educational video (CSEV) as an addition to the current information brochure. Objective In this study, we aimed to evaluate the added effect of the CSEV on IDM regarding CC screening participation among Turkish and Moroccan women aged 30 to 60 years in the Netherlands through a randomized intervention study. Methods Initial respondents were recruited via several social media platforms and invited to complete a web-based questionnaire. Following respondent-driven sampling, respondents were asked to recruit a number of peers from their social networks to complete the same questionnaire. Respondents were randomly assigned to the control (current information brochure) or intervention condition (brochure and CSEV). We measured respondents’ knowledge and attitude regarding CC screening and their intention to participate in the next CC screening round before and after the control or intervention condition. We evaluated the added effect of the CSEV (above the brochure) on their knowledge, attitude, intention, and IDM using intention-to-treat analyses. Results The final sample (n=1564) included 686 (43.86%) Turkish and 878 (56.14%) Moroccan-Dutch women. Of this sample, 50.7% (793/1564) were randomized to the control group (350/793, 44.1% Turkish and 443/793, 55.9% Moroccan) and 49.3% (771/1564) to the intervention group (336/771, 43.6% Turkish and 435/771, 56.4% Moroccan). Among the Turkish-Dutch women, 33.1% (116/350) of the control respondents and 40.5% (136/336) of the intervention respondents consulted the brochure (not statistically significant). Among Moroccan-Dutch women, these percentages were 28.2% (125/443) and 37.9% (165/435), respectively (P=.003). Of all intervention respondents, 96.1% (323/336; Turkish) and 84.4% (367/435; Moroccan) consulted the CSEV. The CSEV resulted in more positive screening attitudes among Moroccan-Dutch women than the brochure (323/435, 74.3% vs 303/443, 68.4%; P=.07). Women, who had never participated in CC screening before, showed significantly more often a positive attitude toward CC screening compared with the control group (P=.01). Conclusions Our short and easily implementable CSEV resulted in more positive screening attitudes, especially in Moroccan-Dutch women. As the CSEV was also watched far more often than the current brochure was read, this intervention can contribute to better reach and more informed CC screening decisions among Turkish- and Moroccan-Dutch women. Trial Registration International Clinical Trial Registry Platform NL8453; https://tinyurl.com/2dvbjxvc