The sense of smell is based on sensory detection of the molecule(s), which is then further perceptually interpreted. A possible measure of olfactory perception is an odor-independent olfactory perceptual fingerprint (OPF) defined by Snitz et al. We aimed to investigate whether OPF can distinguish patients with olfactory dysfunction (OD) due to coronavirus disease (COVID-19) from controls and which perceptual descriptors are important for that separation. Our study included 99 healthy controls and 41 patients. They rated 10 odors using 8 descriptors such as "pleasant," "intense," "familiar," "warm," "cold," "irritating," "edible," and "disgusting." An unsupervised machine learning method, hierarchical cluster analysis, showed that OPF can distinguish patients from controls with an accuracy of 83%, a sensitivity of 51%, and a specificity of 96%. Furthermore, a supervised machine learning method, random forest classifier, showed that OPF can distinguish patients and controls in the testing dataset with an accuracy of 86%, a sensitivity of 64%, and a specificity of 96%. Principal component analysis and random forest classifier showed that familiarity and intensity were the key qualities to explain the variance of the data. In conclusion, people with COVID-19-related OD have a fundamentally different olfactory perception.