The primary shelf life (PSL) of fresh vegan spinach gnocchi packaged under a modified atmosphere (MAP) was investigated. Microbiological, physicochemical, and sensory properties were monitored during storage at three temperatures (4, 8, and 12 °C). The microbial load remained below the limit considered safe (3 log CFU g⁻¹) in all samples during storage at all tested temperatures. Storage time significantly increased the hardness of uncooked gnocchi (p < 0.05) and the water absorption index (p < 0.05). Moreover, at higher storage temperatures, the kinetic rate of hardness decreased in uncooked gnocchi (0.29 N day⁻¹ at 12 °C vs. 0.35 N day⁻¹ at 4 °C). Conversely, in cooked gnocchi, as the storage temperature increased, the rate of hardness acceleration increased. The sensory analysis results varied according to storage temperature, and the Overall Quality Index (OQI), combined with principal component analysis (PCA), was used to determine PSL values. The Arrhenius relationship successfully described the temperature dependence of reaction rate constants, and the calculated Q₁₀ value (3.0) confirmed hardness as the quality attribute most affected by temperature. OQI showed a strong correlation with cooked-gnocchi hardness, and a sensory cutoff of 6.5 was established and confirmed by the sensory panel. The corresponding hardness rejection value was 12.1 N. The PSL was estimated based on sensory and texture criteria, as microbial quality was not a limiting factor. Under non-isothermal cold-chain conditions, PSL was predicted using the time–temperature tolerance (TTT) approach, yielding a value of 42 ± 3 days.