China’s Zero-COVID Policy imposed stringent restrictions on citizens’ mobility to curb the spread of COVID-19. While effective in reducing viral transmission, these measures may have inadvertently delayed or deterred vaccine uptake by fostering a heightened sense of security. This study examines the relationships between intra- and inter-regional travel mobility and individual hesitancy toward COVID-19 vaccines (HCV), leveraging the Baidu Mobility Index and data from a cross-sectional survey of 12,000 participants. Our descriptive analysis reveals that a) individual attitudes toward COVID-19 vaccines are more polarized across regions with different mobility levels than toward vaccines in general and b) regions with higher population mobility exhibit lower levels of hesitancy toward COVID-19 vaccines. Our OLS and IV results further demonstrate that a one-standard-deviation increase in inter-provincial travel rates is associated with a decrease of 0.0112–0.0195 standard deviations in HCV, whereas intra-provincial mobility is not correlated. Overall, this paper suggests prioritizing the roll-out of COVID-19 vaccines or similar initiatives in areas with higher mobility levels, where residents perceive greater risks and exhibit a higher likelihood of seeking vaccination.