Objectives: enhancing uptake of COVID-19 vaccines is an important tool for managing the pandemic. However, in Hong Kong, the COVID-19 vaccination rate in the general population was unsatisfactory during the early phase of the vaccination program. This two-part study aimed to (i) identify barriers and facilitators to receiving vaccinations, and (ii) develop theoretically-informed implementation strategies for promoting uptake. Methods: in part 1, 45 Hong Kong residents who differed in their willingness to vaccinate (willing (n = 15), were unwilling (n = 15), and were hesitant (n = 15)), were interviewed individually in February 2021. They were invited to express their perceptions of receiving the COVID-19 vaccination. The theoretical domains framework (TDF) was applied to guide the interviews and analyses. Behavioral diagnoses from these findings were then used to develop theoretically-informed implementation strategies in part 2, composed of behavior change techniques (BCTs) informed by the established BCT taxonomy. Results: in part 1, the five main barriers were (i) concerns on severe and long-term side effects; (ii) low confidence in the safety and effectiveness due to concerns of their accelerated development; (iii) unclear information on logistical arrangements of the vaccination program; (iv) insufficient data on safety and effectiveness; and (v) perceived low protection ability conferred by the vaccines. The five main facilitators included (i) healthcare professionals recommendations; (ii) news from TV, radio, and newspapers as main sources of trustworthy information; (iii) vaccine-related health education delivered by healthcare professionals; (iv) expectations of resuming to a normal social life; and (v) perceived benefits outweighing risks of mild and short-term side effects. Conclusions: seven implementation strategies were developed in part 2 based on the results above, namely (i) providing trustworthy vaccine-related information and scaling up the promotion; (ii) encouraging healthcare professionals to recommend vaccinations; (iii) giving incentives; (iv) using social influence approaches; (v) allowing a selection of COVID-19 vaccine brands; (vi) increasing accessibility for vaccinations; and (vii) emphasizing social responsibility.