Response surface modeling (RSM) was used to optimize temperature and oxygen concentration during malaxation for obtaining high quality extra virgin olive oils (EVOOs). With this aim, those chemical variables closely related to EVOO quality, such as the phenolic and the volatile compounds, have been previously analyzed and selected. It is widely known that the presence of these substances in EVOOs is highly dependent on genetic, agronomic, and technological aspects. Based on these data, the two parameters were optimized during malaxation of olive pastes of four important Italian cultivars using some phenols and volatile compounds as markers; the optimal temperatures and oxygen levels, obtained by RSM, were as follows for each cultivar: 33.5 °C and 54 kPa of oxygen (Peranzana), 32 °C and 21.3 kPa (Ogliarola), 25 °C and 21.3 kPa (Coratina), and 33 °C and 21.3 kPa (Itrana). These results indicate the necessity to optimize these malaxing parameters for other olive cultivars.