Elevating herd immunity level against rubella is essential to prevent congenital rubella syndrome (CRS). Insufficient vaccination coverage left susceptible pockets among adults in Japan, and the outbreak of rubella from 2012 to 2013 resulted in 45 observed CRS cases. Given a limited stock of rubella-containing vaccine (RCV) available, the Japanese government recommended healthcare providers to prioritize vaccination to those confirmed with low level of immunity, or to those likely to transmit to pregnant women. Although a test-and-vaccinate policy could potentially help reduce the use of the limited stockpile of vaccines, by selectively elevating herd immunity, the cost of serological testing is generally high and comparable to the vaccine itself. Here, we aimed to examine whether random vaccination would be more cost-beneficial than the test-and-vaccinate strategy. A mathematical model was employed to evaluate the vaccination policy implemented in 2012-2013, quantifying the benefit-to-cost ratio to achieve herd immunity. The modelling exercise demonstrated that, while the test-and-vaccinate strategy can efficiently achieve herd immunity when stockpiles of RCV are limited, random vaccination would be a more cost-beneficial strategy. As long as the herd immunity acts as the goal of vaccination, our findings apply to future supplementary immunization strategy.