Virgin olive oil samples stored in the light at ambient temperature, in the dark at ambient temperature, and at low temperature in the dark for 12 months both with and without headspace were separated into recognizable patterns with stepwise linear discriminant analysis. The discrimination with variables volatile and phenolic compounds, free fatty acid (FFA), peroxide values, K232, and K270 revealed a departure of stored oil from freshness and showed significant (p < 0.01) differences between storage conditions. Virgin olive oil stored at low temperature had characteristics closest to fresh oil while oil stored in the light showed the largest departure from freshness. Parameters that exclusively and significantly (p < 0.01) discriminated storage conditions were identified as potential markers of the storage condition. In the presence of oxygen, hexanal was a marker of storage in the light, FFA was a marker for dark storage, and markers of low-temperature storage were acetic acid and pentanal. In the absence of oxygen, octane was the marker for storage in the light whereas tyrosol and hexanol were markers of virgin olive oil stored in the dark, with no marker indicative of low-temperature storage. E-2-Hexenal, K232, and K270 were identified as markers of virgin olive oil freshness.