Background: Fortunately, the majority of COVID-19 patients recover from olfactory dysfunction (OD) within the first couple of weeks. However, from approximately 5% up to 20% continue to suffer from OD even more than 1 year after the onset. Nonetheless, factors associated with long-lasting OD are hardly known. The aim of this study was to identify favourable and disadvantageous markers of persisting OD in COVID-19 patients. Methodology: Sixty-six patients (46 female; mean age: 39.9 years) that suffer from OD longer than 6 months due to laboratory-confirmed SARS-CoV-2 infection have participated in this longitudinal study. Participants completed comprehensive psychophysical chemosensory tests (i.e., Sniffin' Sticks = TDI) and questionnaires twice at our department—on average 219 ± 80 (T-1) and 489 ± 89 (T-2) days after the onset of symptoms, respectively. Olfactory recovery rates were associated with demographic factors and questionnaires using linear regression analysis. Results: Patients below 40 years of age improved better (TDI: 4.1 ± 4.3 vs. 0.7 ± 5.8; p = 0.008) and achieved statistically significant higher scores (TDI: 31.5 ± 4.0 vs. 27.3 ± 6.7; p = 0.033) regarding psychophysical chemosensory tests. Furthermore, linear regression analysis revealed that parosmia was associated with worse orthonasal smell function (T-1: β = −0.346, p = 0.004; T-2: β = −0.384, p = 0.001), especially concerning identification subtest (T-1: β = −0.395, p = 0.001; T-2: β = −0.398, p < 0.001). Moreover, increasing parosmia between T-1and T-2 led to worse orthonasal olfactory function (β = −0.294, p = 0.016). Conclusions: Older age and parosmia seem to be unfavourable factors of persisting OD in COVID-19 patients.