Background There are concerns that vaccine hesitancy may impede COVID-19 vaccine rollout and prevent the achievement of herd immunity. Vaccine hesitancy is a delay in acceptance or refusal of vaccines despite their availability. Objective We aimed to identify which people are more and less likely to take a COVID-19 vaccine and factors associated with vaccine hesitancy to inform public health messaging. Methods A Canadian cross-sectional survey was conducted in Canada in October and November 2020, prior to the regulatory approval of the COVID-19 vaccines. Vaccine hesitancy was measured by respondents answering the question “what would you do if a COVID-19 vaccine were available to you?” Negative binomial regression was used to identify the factors associated with vaccine hesitancy. Cluster analysis was performed to identify distinct clusters based on intention to take a COVID-19 vaccine, beliefs about COVID-19 and COVID-19 vaccines, and adherence to nonpharmaceutical interventions. Results Of 4498 participants, 2876 (63.9%) reported COVID-19 vaccine hesitancy. Vaccine hesitancy was significantly associated with (1) younger age (18-39 years), (2) lower education, and (3) non-Liberal political leaning. Participants that reported vaccine hesitancy were less likely to believe that a COVID-19 vaccine would end the pandemic or that the benefits of a COVID-19 vaccine outweighed the risks. Individuals with vaccine hesitancy had higher prevalence of being concerned about vaccine side effects, lower prevalence of being influenced by peers or health care professionals, and lower prevalence of trust in government institutions. Conclusions These findings can be used to inform targeted public health messaging to combat vaccine hesitancy as COVID-19 vaccine administration continues. Messaging related to preventing COVID among friends and family, highlighting the benefits, emphasizing safety and efficacy of COVID-19 vaccination, and ensuring that health care workers are knowledgeable and supported in their vaccination counselling may be effective for vaccine-hesitant populations.