In order to differentiate the extra virgin olive oils (EVOO) of different origin of purchase, such as monovarietal Italian EVOO with protected denomination of origin (PDO) and commercial-blended EVOO purchased in supermarkets, a number of samples was subjected to the analysis of volatile aroma compounds by both targeted gas chromatography/mass spectrometry (GC-MS) and untargeted profiling by comprehensive two-dimensional gas chromatography/mass spectrometry (GC×GC-TOF-MS), analysis of phenols by targeted high-performance liquid chromatography/mass spectrometry (HPLC-DAD-ESI/MS), and quantitative descriptive sensory analysis. Monovarietal PDO EVOOs were characterized by notably higher amounts of positive LOX-derived C6 and C5 volatile compounds, which corresponded to the higher intensities of all the assessed positive fruity and green odor sensory attributes. Commercial-blended EVOOs had larger quantities of generally undesirable esters, alcohols, acids, and aldehydes, which coincided with the occurrence of sensory defects in many samples. Many minor volatile compounds that were identified by GC×GC-TOF-MS were found to differentiate each of the two investigated groups. The differences between the groups with respect to phenols and taste characteristics were evident, but less pronounced. The results that were obtained in this study have undoubtedly confirmed the existence of the large heterogeneity of oils that are sold declared as EVOO. It was shown that GC-MS, GC×GC-TOF-MS, and HPLC-DAD-ESI/MS analyses have complementary outputs, and that their use in combination has advantages in supporting the results of sensory analysis and objectively differentiating these groups of EVOO.