Healthcare workers are at the frontline of the COVID-19 pandemic and have been identified as a priority target group for COVID-19 vaccines. This study aimed to determine the COVID-19 vaccination intention among nurses and midwives in Cyprus and reveal the influential factors that affected their decision. An Internet-based cross-sectional survey was conducted between December 8 and 28, 2020. Data collection was accomplished using a self-administered questionnaire with questions about socio-demographic characteristics, questions assessing general vaccination-related intentions and behaviors, and the intention to accept COVID-19 vaccination. A sample of 437 responders answered the survey, with 93% being nurses and 7% midwives. A small proportion of the participants would accept a vaccine against COVID-19, while 70% could be qualified as “vaccine hesitant.” The main reasons for not receiving the COVID-19 vaccine were concerns about the vaccine's expedited development and fear of side effects. More females, individuals with a larger median age, and a higher number of years of working experience, intended to accept the COVID-19 vaccination, compared with those not intended to accept and undecided groups (p < 0.01). Having a seasonal flu vaccination in the last 5 years, receiving the vaccines recommended for health professionals, and working in the private sector were associated with a higher probability of COVID-19 vaccination acceptance. A considerable rate of nurses and midwives in Cyprus reported unwillingness to receive a COVID-19 vaccine due to vaccine-related concerns. Our findings highlight the need for forthcoming vaccination campaigns and programs to tackle coronavirus vaccine hesitancy barriers to achieve the desirable vaccination coverage.