China is considering to offer COVID-19 vaccination for children aged 6–35 months. This study investigated the changes in COVID-19 vaccine acceptability and associated factors among parents with children aged 6–35 months in 2020 and 2021. Two rounds of cross-sectional online surveys were conducted among adult factory workers in Shenzhen, China. A subset of 208 (first round) and 229 (second round) parents with at least one child aged 6–35 months was included in the study. Parental acceptability of COVID-19 vaccination increased significantly from 66.8% in the first round to 79.5% in the second round (p = 0.01). Positive attitudes, perceived subjective norm, and perceived behavioral control were associated with higher parental acceptability in both rounds of surveys (p values ranged from <0.001 to 0.003). A negative association of negative attitudes with parental acceptability was observed in the second round (p = 0.02). No significant associations of exposure to information related to COVID-19 vaccination on social media with parental acceptability was found in either round of survey. Expanding the existing COVID-19 vaccination programs to cover children aged 6–35 months is necessary in China. Future programs should focus on modifying perceptions among parents to promote COVID-19 vaccination for children in this age group.