Introduction: Chronic pain is increasingly recognized as part of long COVID syndrome, mainly in the form of myalgias. However, chronic pain has several forms, and according to our clinical experience, COVID-19 survivors suffer from numerous painful syndromes, other than myalgias. The aim of our study was to estimate the prevalence of chronic pain, describe the commonest painful syndromes and identify pain determinants in a random population of COVID-19 survivors. Methods: This was a cross-sectional study conducted at the Medical School, University of Cyprus. A random population of 90 COVID-19 survivors was recruited. Demographic and COVID-19 related clinical characteristics were recorded. The painDETECT and DN4 questionnaires were used to evaluate the painful syndromes. Results: The prevalence of chronic pain was estimated to be 63.3%. The most common site of pain was low back (37.8%), followed by joints (28.9%) and neck (12.2%). Patients with chronic pain compared to subjects without pain were older (50.5 ± 15.9 versus 42.2 ± 12.6, p = 0.011) and more likely to be female (71.9% versus 45.5%, p = 0.013). One in six subjects (16.7%) reported new-onset pain post COVID-19. The prevalence of neuropathic pain was estimated to be 24.4%. After adjusting for age and gender, headache during COVID-19 was a statistically significant predictor of neuropathic pain, increasing 4.9 times (95% 1.4–16.6, p = 0.011) the odds of neuropathic pain. Conclusion: Chronic pain—especially neuropathic—is widely prevalent in COVID-19 survivors. One in six subjects will develop new-onset pain that will persist beyond the acute phase of the disease and, therefore, should be considered a symptom of long COVID syndrome.