Thyme honey is the most appreciated unifloral Greek honey in Greece as well as around the world. In an effort to investigate the headspace composition of this type of honey, 28 samples were analyzed by means of solid-phase microextraction coupled to a gas chromatography-mass spectrometry system. The botanical origin of the samples was ascertained by pollen analysis, and samples displayed relative frequencies of thyme pollen between 18 and 41%. A total of 62 compounds were isolated, and phenylacetaldehyde was the most abundant (32.9% of the total peak area). Possible botanical markers are 1-phenyl-2,3-butanedione (13.4%), 3-hydroxy-4-phenyl-2-butanone, 3-hydroxy-1-phenyl-2-butanone (14.7%), phenylacetonitrile (4.8%), and carvacrol (0.9%), since these compounds are found only in thyme honey. Additionally, high proportions of phenylacetaldehyde are also characteristic ( F = 12.282, p < 0.001). The average concentrations of seven compounds were significantly different ( p < 0.05), namely phenylacetaldehyde, acetophenone, octanoic acid, carvacrol, phenylethyl alcohol, nonanal, and hexadecane. Applying principal component analysis to the data, six components were extracted, explaining 85.4% of the total variance. The first component explained 46.2% of the total variance and was positively correlated to phenylacetaldehyde, nonanoic acid, acetophenone, decanoic acid, benzaldehyde, phenylacetonitrile, isophorone, and nonanal. The extracted components were used as variables to the discriminant analysis, which showed good discrimination, especially for samples from Crete. A leave-one-out classification showed 85.7% of cross-validated grouped cases correctly classified. These results are promising to establish a discrimination model for these geographical regions. This is crucial for local beekeeper corporations on their effort to produce honey with geographical origin label.