The prevailing COVID-19 pandemic has dramatically affected the mental health and well-being of individuals. This cross-sectional study aimed to assess the perceived fear of COVID-19 among older adults in Poland and identify subpopulations with the highest risk of potential mental health disorders. The study was conducted in November–December 2020 on 500 people aged ≥60 years (mean M = 67.9, standard deviation SD = 4.2). In order to collect information on participants’ characteristics and COVID-19-related information, they were asked to complete a questionnaire based on recorded telephone calls. Perceived fear of COVID-19 was measured using our generated and validated seven-item tool: “Scale of fear of COVID-19 infection”, which ranged from 7 to 35. Multiple linear regression was performed to identify factors associated with the perceived fear of COVID-19. Our results showed that the highest level of fear of COVID-19 infection was observed among women (p = 0.025) and patients taking anticoagulants (p = 0.004). Moreover, older adults with higher anxiety levels were more likely to be fearful of COVID-19 (according to the GAS-10 scale; p < 0.001). These findings may help policy makers and healthcare workers to adapt and implement better mental health strategies to help the elderly fight fear and anxiety during the prevailing pandemic.