Introduction: A cluster vaccination coverage survey was conducted in two districts, Dowa and Ntchisi, in Malawi to measure the vaccination coverage of children 12–23 months old and identify factors impacting the utilization of vaccination service. Methods: A cross-sectional descriptive cluster survey with 30 clusters and 10 children per cluster was administered in each district including a total of 601 children surveyed. 57 village heads and 60 health surveillance assistants (HSAs) were also interviewed. Findings: The vaccination card availability was very high in both districts (94%). Vaccination coverage by card plus history of mothers was very high, above 93% for all antigens, and the coverage by card alone was also high with a range of pentavalent1 coverage of 91% in Ntchisi and 83% in Dowa to measles coverage of 81% and 83% in Dowa and Ntchisi respectively. However, the percentage of valid doses administered to fully immunized children was low (60% in Dowa and 49% in Ntchisi). About 10% of the pentavalent1 doses in Dowa and 9% in Ntchisi were administered before six weeks of age and 7% and 8% of the pentavalent3 doses in Dowa and Ntchisi districts respectively were administered in less than 28 days after pentavalent2. Similarly, 15% of measles doses in both Dowa and Ntchisi districts were administered before 270 days. The main reason for no vaccination was vaccine stock outs at health facility level. The majority of village heads are satisfied with the vaccination service in their communities. Health surveillance assistants (HSAs), village heads and religious leaders all play major roles in mobilization for vaccination service in the two districts. Conclusion: Dowa and Ntchisi districts have high vaccination coverage, however many children receive invalid doses. This finding calls for immediate action to educate the service providers on administration of valid doses.