Modifications of virgin olive oil subjected to accelerated storage were evaluated by HS-SPME analysis. To find a suitable marker of oxidative degradation, the volatile compounds showing variable concentration during the oxidative process have been identified and quantified by SPME coupled to GC-MS and GC-FID, respectively. The SPME analysis results were then compared with the parameters usually applied to assess the oxidative status of lipids, such as peroxide value, spectrophotometric absorbance, and loss of unsaturated fatty acids. Finally, the assessment of nonanal has been suggested as a marker of oxidative degradation. This rapid, inexpensive, and reliable method may allow screening of oils prior to testing by a panel of assessors.