Background: Vaccine hesitancy is caused by a variety of factors, which are complex and multifaceted. The perceived risks of vaccines, the relationship between parents and health-care providers, and the social norm of vaccination are all factors that influence vaccine decision making. Objective: This study aimed to conclude the prevalence of vaccine indecision amongst parents visiting PHC in Al-Madinah city, to identify socio-demographic determinants of vaccine hesitancy and to recognize agents and host-related factors, which leads to hesitancy. Methods: A cross-sectional research was implemented on parents who attended the PHC using a valid questionnaire filled by interviewing the parents. All data was confirmed manually then was implied and entered into SPSS software. Then the data were analyzed using the appropriate statistical test. Results: Vaccines can protect children from dangerous diseases, according to 98.1% of the 375 people who took part in our study. 88.5% of parents preferred to get their children vaccinated with all of the vaccines that are recommended. 69.9% of participants had ever been hesitant or unwilling to have their child vaccinated. 9.6% of parents were unable to get their child vaccinated due to distance, clinic timing, time needed to get the clinic or wait at the clinic, and/or the cost of getting to the clinic. Conclusion: Finally, our findings demonstrated that vaccine apprehension is a prominent issue among parents in Saudi Arabia. We discovered that vaccine fear is widespread, and that it spiked during the COVID-19 pandemic.