Maintaining the quality of extra virgin olive oil (EVOO) during storage is essential for preserving its nutritional, sensory, and commercial value. This study evaluated the storage stability of 192 EVOO samples from twelve cultivars harvested at green and ripe maturity stages and stored under ambient (25 °C) and accelerated (40 °C) conditions for up to twelve months. Quality evolution was assessed using conventional physicochemical analyses, sensory evaluation, and near-infrared (NIR) spectroscopy (1100–2498 nm) combined with chemometric approaches, including principal component analysis (PCA), ordinary least squares (OLS), and stepwise decorrelation of the variables (SELECT), to identify informative wavelengths and develop predictive models for quality monitoring. Storage significantly affected oxidation indices, phenolic compounds, pigments, and sensory attributes, with deterioration occurring more rapidly under accelerated conditions. Phenolic-rich cultivars, including Royuela, Picual, and Koroneiki, exhibited greater oxidative stability than Hojiblanca, Manzanilla, and Arbequina. The developed NIR models accurately predicted key quality parameters, with R² values ranging from 0.94 to 0.98, while successfully discriminating oils according to cultivar, maturity stage, and storage conditions. The spectral region around 2354 nm was identified as a key marker of oxidation, showing progressive absorbance changes associated with peroxide formation and quality deterioration during storage. These results demonstrate that NIR spectroscopy coupled with advanced chemometric analysis provides a rapid, non-destructive, and reliable approach for real-time monitoring of EVOO quality, freshness, and shelf-life, supporting efficient quality control and sustainable olive oil production.