Background: In the last 20 years, Brazil has undergone dramatic changes in terms of socioeconomic development and health care. In the first decade of the 2000s, the Ministry of Health (MoH) developed a series of programs focused on reducing infant mortality, including the Family Health Program as a national policy for primary care. In this paper, we propose a method to correct underreporting of deaths and live births. After vital statistics are corrected, infant mortality trends are analyzed for the period 2000–2010 by macro-geographical region. Methods: A proactive search of live births and deaths was carried out in the Amazon and Northeast regions in 2010 to find vital events that occurred in 2008 and were not reported to the Ministry of Health. The probabilistic sample of 133 municipalities was stratified by adequacy of vital information reporting. For each municipality, the adequacy analysis was based on the reported age-standardized mortality rate per 1,000 population and the ratio between reported and estimated live births. Correction factors were estimated by strata based on additional vital events found in the proactive search. The procedure was generalized to correct municipal vital statistics for the period 2000–2010. Results: In the proactive search, 35% of non-reported deaths were found within the health system (hospitals and other health establishments), but 28% were found in non-official sources, like illegal cemeteries. In areas of extreme poverty and unreliable vital information, the estimated completeness of infant death reporting was only 33%. After correction of vital information, the estimated infant mortality rate decreased from 26.1 in 2000 to 16.0 in 2010, with an annual rate of decrease of 4.7%, greater than the required rate to achieve the Millennium Development Goal. Among Brazilian regions, the Northeast showed the largest decrease, from 38.4 to 20.1 per 1,000 live births. Conclusions: The proactive search for vital events was shown to be a good strategy both in terms of understanding local irregularities and for correcting vital statistics. The methodology could be applied in other countries to routinely assess the pattern and extent of birth and death under-registration in order to improve the utility of these data to inform health policies.