Mass vaccination campaigns with the oral poliovirus vaccine targeting children aged <5 years are a critical component of the global poliomyelitis eradication effort. Monitoring the coverage of these campaigns is essential to allow corrective action, but current approaches are limited by their cross-sectional nature, nonrandom sampling, reporting biases, and accessibility issues. We describe a new Bayesian framework using data augmentation and Markov chain Monte Carlo methods to estimate variation in vaccination coverage from children's vaccination histories investigated during surveillance for acute flaccid paralysis. We tested the method using simulated data with at least 200 cases and were able to detect undervaccinated groups if they exceeded 10% of all children and temporal changes in coverage of ±10% with greater than 90% sensitivity. Application of the method to data from Pakistan for 2010-2011 identified undervaccinated groups within the Balochistan/Federally Administered Tribal Areas and Khyber Pakhtunkhwa regions, as well as temporal changes in coverage. The sizes of these groups are consistent with the multiple challenges faced by the program in these regions as a result of conflict and insecurity. Application of this new method to routinely collected data can be a useful tool for identifying poorly performing areas and assisting in eradication efforts.