Virgin olive oils produced at wide ranges of malaxation temperatures (15, 30, 45, and 60 °C) and times (30, 60, 90, and 120 min) in a complete factorial experimental design were discriminated with stepwise linear discriminant analysis (SLDA) revealing differences with processing conditions. Virgin olive oils produced at 15 and 60 °C for 30 min showed the most significant (p < 0.01) differences. Discrimination was based upon volatile and phenolic compounds detected in olive oils, peroxide value (PV), free fatty acids (FFA), ultraviolet (UV) absorbances, and oil yield. There were different discriminating variables for processing conditions illustrating the dependence of virgin olive oil quality on malaxation time and temperature. Volatile compounds were the dominant discriminating variables. Common oxidation indicators of olive oil (PV, K232, and K270) were not among the variables that significantly (p < 0.01) changed with malaxation time and temperature. Variables that discriminated both malaxation time and temperature were hexanal, 3,4-dihydroxyphenyl ethyl alcohol'decarboxymethyl elenolic acid dialdehyde (3,4-DHPEA-DEDA) and FFA, whereas 1-penten-3-ol, E-2-hexenal, octane, tyrosol, and vanillic acid significantly (p < 0.01) changed with temperature only and Z-2-penten-1-ol, (+)-acetoxypinoresinol, and oil yield changed with time only. Virgin olive oil quality was significantly influenced by malaxation temperature, whereas oil yield discriminated malaxation time. This study demonstrates the two modes of hexanal formation: enzymatic and nonenzymatic during virgin olive oil extraction.