Vaccine hesitancy is a major barrier to achieving large-scale COVID-19 vaccination. We report trends in vaccination intention and associated determinants from surveys in the adult general population in Greece. Four cross-sectional phone surveys were conducted in November 2020 and February, April and May 2021 on nationally representative samples of adults in Greece. Multinomial logistic regression was used on the combined data of the surveys to evaluate independent predictors of vaccination unwillingness/uncertainty. Vaccination intention increased from 67.6% in November 2020 to 84.8% in May 2021. Individuals aged 65 years or older were more willing to be vaccinated (May 2021: 92.9% vs. 79.5% in 18–39 years, p < 0.001) but between age-groups differences decreased over time. Vaccination intention increased substantially in both men and women, though earlier among men, and was higher in individuals with prograduate education (May 2021: 91.3% vs. 84.0% up to junior high). From multivariable analysis, unwillingness and/or uncertainty to be vaccinated was associated with younger age, female gender (in particular in the April 2021 survey), lower educational level and living with a child ≤12 years old. Among those with vaccine hesitancy, concerns about vaccine effectiveness declined over time (21.6% in November 2020 vs. 9.6% in May 2021, p = 0.014) and were reported more often by men; safety concerns remained stable over time (66.3% in November 2020 vs. 62.1% in May 2021, p = 0.658) and were reported more often by women. In conclusion, vaccination intention increased substantially over time. Tailored communication is needed to address vaccine hesitancy and concerns regarding vaccine safety.