The vaccine confidence index in Japan is one of the lowest worldwide. This study aimed to examine the proportion of COVID-19 vaccine hesitancy in the Japanese population using a larger sample and more robust statistical methods than previously, and to identify factors associated with vaccine hesitancy. We conducted a nationwide, cross-sectional Internet survey on 8-26 February 2021, and calculated the proportion and odds ratios for vaccine hesitancy. Among 23,142 responses analyzed, the proportion of COVID-19 vaccine hesitancy was 11.3% (10.9-11.7%). The proportion was higher among younger respondents and female respondents, and especially among younger female respondents (15.6%) compared with the lowest proportion among older male respondents (4.8%). The most cited reason for not getting vaccinated was concerns about adverse reactions in more than 70% of the respondents. The proportion of COVID-19 vaccine hesitancy in Japan was comparable to that in previous studies overseas, and the proportion among younger respondents was more than double that among older respondents. Factors associated with the hesitancy were female sex, living alone, low socioeconomic status, and presence of severe psychological distress, especially among older respondents. Thus, adequate measures should be taken to ensure that vaccines are delivered to people with these factors.