This study investigated the relationship between fear of COVID-19, previous exposure to COVID-19, perceived vulnerability to disease, sleep quality, and psychological distress among healthcare workers (HCWs) in Taif city in Saudi Arabia, which has a population of 702,000 people. A cross-sectional study design was adopted. HCWs (n = 202) completed a survey containing the Fear of COVID-19 Scale (FCV-19S), Perceived Vulnerability to Disease (PVD), Pittsburgh Sleep Quality Index (PSQI), and Depression, Anxiety, and Stress Scale (DASS-21). FCV-19S and sleep quality were significant predictors for psychological distress. Female gender was a significant predictor for depression and stress. Single, divorced, and widowed marital status were predictive for anxiety. FCV-19S was weakly correlated with PVD but moderately with depression, anxiety, and stress. Of the two PVD subscales, perceived infectability was weakly correlated with psychological distress. PVD and previous experience with COVID-19 were not significant predictors. Sleep quality and FCV-19S were major predictors of psychological distress. Findings indicated that poor sleep quality was strongly associated with psychological distress, while fear of COVID-19 had a moderate association. Such results support the need to design and implement psychological programs to assist HCWs in dealing with the psychological impact of this ongoing pandemic.