Headspace solid phase microextraction in combination with comprehensive two-dimensional gas chromatography coupled to time-of-flight mass spectrometry (HS-SPME-GC × GC-TOF-MS) was used for the detailed investigation of the impact of malolactic fermentation (MLF) using three commercial Oenococcus oeni strains on the volatile composition of Vitis vinifera cv. Pinotage wines. GC × GC allowed the identification of 115 volatile compounds, including both major constituents and trace-level compounds, in a single analysis. A number of compounds differing in mean concentration levels between the control wines and those fermented with different starter cultures were shown for the first time to be influenced by MLF and/or the bacterial strain. Principal component analysis (PCA) provided excellent separation between the wines fermented with different MLF starter cultures and the control wine. Significantly different levels for some volatile compounds in wines fermented with one of the LAB starter cultures could be indicative of metabolic differences of this strain.