BACKGROUND: The estimates of vaccination coverage are measured from administrative data and from population based survey. While both card-based and recall data are collected through population survey, and the recall is when the card is missing, the preferred estimates remain of the card-based due to limited validity of parental recalls. As there is a concern of missing cards in poor settings, the evidence on validity of parental recalls is limited and varied across vaccine types, and therefore timely and needed. We validated the recalls against card-based data based on population survey in Tanzania. METHODS: We used a cross-sectional survey of about 3000 households with women who delivered in the last 12 months prior to the interview in 2012 from three regions in Tanzania. Data on the vaccination status on four vaccine types were collected using two data sources, card and recall-based. We compared the level of agreement and identified the recall bias between the two data sources. We further computed the sensitivity and specificity of parental recalls, and used a multivariate logit model to identify the determinants of parental recall bias. RESULTS: Most parents (85.4%) were able to present the vaccination cards during the survey, and these were used for analysis. Although the coverage levels were generally similar across data sources, the recall-based data slightly overestimated the coverage estimates. The level of agreement between the two data sources was high above 94%, with minimal recall bias of less than 6%. The recall bias due to over-reporting were slightly higher than that due to under-reporting. The sensitivity of parental recalls was generally high for all vaccine types, while the specificity was generally low across vaccine types except for measles. The minimal recall bias for DPT and measles were associated with the mother's age, education level, health insurance status, region location and child age. CONCLUSION: Parental recalls when compared to card-based data are hugely accurate with minimal recall bias in Tanzania. Our findings support the use of parental recall collected through surveys to identify the child vaccination status in the absence of vaccination cards. The use of recall data alongside card-based estimates also ensures more representative coverage estimates.