Authenticity and the geographical origin of wines are terms of great importance for consumers and producers. This work is focused on distinguishing between red wines from Poland and from other European countries, notably France, Italy and Spain. To achieve this goal, we determined aroma compounds in wines from different countries by headspace solid-phase microextraction/gas chromatography-mass spectrometry. The content of hexan-1-ol in Polish wines was significantly higher (about twice as high) than in French, Italian and Spanish wines. Linear discriminant analysis (LDA) showed that 3-(methylsulfanyl)propane-1-ol, hexan-1-ol, ethyl phenylacetate and ethyl 2-hydroxy-4-methylpentanoate were the most discriminant variables for distinguishing between wines from Poland and from other European countries. Hierarchical cluster analysis (HCA) revealed that Polish wines were separated thoroughly from the other wines based on ethyl phenylacetate, hexan-1-ol, ethyl 2-hydroxy-4-methylpentanoate, (E)-3-hexen-1-ol, 2-phenylethanol and 3-(methylsulfanyl)propan-1-ol, which is important for preventing possible frauds.