Measles is a highly contagious disease that can be effectively prevented through vaccination. The recent increase in vaccination coverage was successful in reducing the mortality globally of the disease by 74%. As a whole, the Americas have been considered a disease-free zone. However, it is known that if an immunization programs fails, there will be an accumulation of susceptible people that can lead to disease outbreaks. Recently, both the United States and Brazil faced outbreaks of measles. The present study aims to identify the determining factors of non-vaccination in Brazil in two different vaccination coverage moments, to provide clues as to the causes of current outbreaks. Data were drawn from five population-based cross-sectional studies that surveyed a representative sample of preschool children from 1987 to 2007 (9585 children in total). To assess children's vaccination status, two different information sources were used: information provided by mothers and information from children's health cards. Multivariate analyses with logistic binary regression models were conducted. After adjustment for confounding factors, it was observed that in 1987, with 48.2% vaccination coverage, socioeconomic, maternal, nutritional factors and access to health facilities were important, while in 2007 (96.7% coverage), nutritional and maternal factors were important. Distinct patterns of determinants of non-vaccination were also found. In addition, the low coverage in 1987 resulted in a current pool of adults who were not immunized as children; this may have contributed to the beginning of the current Brazilian outbreak. Globally, there are two standards of vaccination coverage (low and high). Therefore, discussion of the determinants of non-vaccination is important. Our findings suggest vulnerable groups should receive special attention to ensure they are protected. It is also important to consider the possible impact of pools of adults not immunized.