A total of 33 virgin olive oil samples of the two main Tunisian cultivars, Chemlali and Chétoui, were characterized by their volatile compounds. The olive oil samples were obtained from olives harvested at four stages of ripeness in costal and inland farms of different geographical places. Major volatiles, mostly C6 and C5 compounds produced from linolenic and linoleic acids through the lipoxygenase cascade, were quantified by solid-phase microextraction-gas chromatography. Mathematical procedures allowed for the determination of the volatiles that not only are able to discriminate the olive oils by their olive cultivar (hexanal, E-2-hexenal, and total ketones) and ripeness (pentanal and 1-penten-3-one) but also contribute to their distinctive aroma. Finally, an electronic nose based on metal oxide sensors was checked for a rapid and at-line implementation of Tunisian olive oil varietal traceability. The classification of the samples by the sensors was explained by their sensitivity to volatiles E-2-hexanal, hexanal, 1-penten-3-one, ethanol, and Z-3-hexenol. Multivariate procedures of discriminant analysis and principal component analysis were used in the study.