The aim of this study was to determine volatile compounds in red wines of Zweigelt and Rondo varieties using HS-SPME/GC-MS and to find a marker and/or a classification model for the assessment of varietal authenticity. The wines were produced by using five commercial yeast strains and two types of malolactic fermentation. Sixty-seven volatile compounds were tentatively identified in the test wines; they represented several classes: 9 acids, 24 alcohols, 2 aldehydes, 19 esters, 2 furan compounds, 2 ketones, 1 sulfur compound and 8 terpenes. 3,7-dimethyl-1,5,7-octatrien-3-ol (hotrienol) was found to be a variety marker for Zweigelt wines, since it was detected in all the Zweigelt wines, but was not present in the Rondo wines at all. The relative concentrations of volatiles were used as an input data set, divided into two subsets (training and testing), to the support vector machine (SVM) and k-nearest neighbor (kNN) algorithms. Both machine learning methods yielded models with the highest possible classification accuracy (100%) when the relative concentrations of all the test compounds or alcohols alone were used as input data. An evaluation of the importance value of subsets consisting of six volatile compounds with the highest potential to distinguish between the Zweigelt and Rondo varieties revealed that SVM and kNN yielded the best classification models (F-score of 1, accuracy of 100%) when 3-ethyl-4-methylpentan-1-ol or 3,7-dimethyl-1,5,7-octatrien-3-ol (hotrienol) or subsets containing one or both of them were used. Moreover, the best SVM model (F-score of 1) was built with a subset containing 2-phenylethyl acetate and 3-(methylsulfanyl)propan-1-ol.