Background: Mathematical models have formalized how free-rider effects can threaten the stability of high vaccine coverage levels under established voluntary vaccination programs. However, little research has addressed the question of when free-riding begins to develop when a new vaccine is first introduced in a population. Methodology/Principal Findings: Here, we combine a game theoretical model of vaccinating behavior with an agestructured compartmental model to analyze rational vaccinating behavior in the first years of a universal immunization program, where a new vaccine is free to all children of a specified age. The model captures how successive birth cohorts face different epidemiological landscapes that have been shaped by the vaccinating decisions of previous birth cohorts, resulting in a strategic interaction between individuals in different birth cohorts. The model predicts a Nash equilibrium coverage level of 100% for the first few birth cohorts under the new program. However, free-riding behavior emerges very quickly, with the Nash equilibrium vaccine coverage dropping significantly within 2-5 years after program initiation. Subsequently, a rich set of coupled dynamics between infection prevalence and vaccinating behaviors is possible, ranging from relatively stable (but reduced) coverage in later birth cohorts to wide fluctuations in vaccine coverage from one birth cohort to the next. Individual tolerance for vaccine risk also starts out at relatively high levels before dropping significantly within a few years. Conclusions/Significance: These results suggest that even relatively new immunization programs can be vulnerable to drops in vaccine coverage caused by vaccine scares and exacerbated by herd immunity effects, necessitating vigilance from the start.