The present work deals with the characterization of volatile organic compounds (VOCs) in wines from the Slovak Tokaj wine region. Studied wine samples were divided into three groups—varietal wines from registered Tokaj vine varieties, film wines Tokajské samorodné dry, and naturally sweet botrytized wines Tokaj selections. The VOCs from wines were extracted using optimized solid phase microextraction (SPME) and analyzed by comprehensive two-dimensional gas chromatography (GC×GC) coupled to high-resolution time-of-flight mass spectrometry (HRTOF-MS). In total, 176 VOCs were identified in all 46 studied samples. It was found that the total number of VOCs in varietal wines was generally higher than in botrytized wines. All three studied categories showed characteristic VOC profiles with significant differences. Varietal wines were characterized by higher concentrations of esters and terpenoids originating from grapes. The presence of γ-octalactone, (E)-6-methylhept-2-en-4-one, and lack of benzaldehyde were typical for Tokajské samorodné dry. Tokaj selections expressed the highest concentration of diethyl malate, benzaldehyde, and furfurals. Several interesting trends were also observed. The concentration of fermentation products was highest in varietal wines, while long-term matured Tokaj special wines were typified by the presence of compounds related to noble-rotten raisins (2-phenylacetaldehyde, ethyl 2-phenylacetate, and 2-phenylethanol), wood (cis-whisky lactone), and aging (1,1,6-trimethyl-2H-naphthalene, furfural, and 5-methylfurfural).