The government of Kenya has launched a phased rollout of COVID-19 vaccination. A major barrier is vaccine hesitancy; the refusal or delay of accepting vaccination. This study evaluated the level and determinants of vaccine hesitancy in Kenya. We conducted a cross-sectional study administered through a phone-based survey in February 2021 in four counties of Kenya. Multilevel logistic regression was used to identify individual perceived risks and influences, context-specific factors and vaccine-specific issues associated with COVID-19 vaccine hesitancy. COVID-19 vaccine hesitancy in Kenya was high: 36.5%. Factors associated with vaccine hesitancy included: Rural regions, perceived difficulty in adhering to government regulations on COVID-19 prevention, no perceived COVID-19 infection risk, concerns regarding vaccine safety and effectiveness, and religious and cultural reasons. There is a need for the prioritization of interventions to address vaccine hesitancy and improve vaccine confidence as part of the vaccine roll-out plan. These messaging and/or interventions should be holistic to include the value of other public health measures, be focused and targeted to specific groups, raise awareness on the risks of COVID-19 and effectively communicate the benefits and risks of vaccines.