An estimated 110,000 babies are born with congenital rubella syndrome (CRS) worldwide annually; a significant proportion of cases occur in Southeast Asia. Rubella vaccine programs have led to successful control of rubella and CRS, and even the elimination of disease in many countries. However, if vaccination is poorly implemented it might increase the number of women reaching childbearing age who remain susceptible to rubella and thereby paradoxically increase CRS. We used an age-structured transmission model to compare seven alternative vaccine strategies for their impact on reducing CRS disease burden in East Java, a setting which is yet to implement a rubella vaccine program. We also investigated the robustness of model predictions to variation in vaccine coverage and other key epidemiological factors. Without rubella vaccination, approximately 700 babies are estimated to be born with CRS in East Java every year at an incidence of 0.77 per 1000 live births. This incidence could be reduced to 0.0045 per 1000 live births associated with 99.9% annual reduction in rubella infections after 20 years if the existing two doses of measles vaccine are substituted with two doses of measles plus rubella combination vaccine with the same coverage (87.8% of 9-month-old infants and 80% of 6-year-old children). By comparison a single dose of rubella vaccine will take longer to reduce the burden of rubella and CRS and will be less robust to lower vaccine coverage. While the findings of this study should be informative for settings similar to East Java, the conclusions are dependent on vaccine coverage which would need consideration before applying to all of Indonesia and elsewhere in Asia.