The exposure of foodborne pathogens such as Salmonella enterica to a sub-lethal stress may protect bacterial cells against distinct stresses during the production of leafy greens, which can constitute potential health hazards to consumers. In this study, we evaluated how the prior exposure of S. enterica to sub-lethal food processing-related stresses influenced its subsequent persistence on baby spinach under cold (4 °C for 7 days) and temperature abuse (37 °C for 2 h + 4 °C for 7 days) conditions. We also compared the survival characteristics of pre-stressed S. enterica and Enterococcus faecium NRRL B-2354 as its surrogate on baby spinach. A cocktail of three S. enterica serovars, as well as S. Typhimurium ATCC 14028 wild type and its ΔrpoS mutant, and E. faecium NRRL B-2354, was first exposed to sub-lethal desiccation, oxidation, heat shock, and acid stresses. Afterward, baby spinach was inoculated with unstressed or pre-stressed cells at 7.0 log CFU/sample unit, followed by 7-day storage under cold and temperature abuse conditions. The unstressed S. enterica (fresh cells in sterile 0.85% saline) decreased rapidly within the first day and thereafter persisted around 5.5 log CFU/sample unit under both conditions. The desiccation-stressed S. enterica showed the highest bacterial counts (p < 0.05) compared to other conditions. The unstressed S. enterica survived better (p < 0.05) than the oxidation- and acid-stressed S. enterica, while there were no significant differences (p > 0.05) between the unstressed and heat-shocked S. enterica. Unlike the wild type, temperature abuse did not lead to the enhanced survival of the ΔrpoS mutant after exposure to desiccation stress, indicating that the rpoS gene could play a critical role in the persistence of desiccation-stressed S. enterica subjected to temperature abuse. E. faecium NRRL B-2354 was more persistent (p < 0.05) than the pre-stressed S. enterica under both conditions, suggesting its use as a suitable surrogate for pre-stressed S. enterica by providing a sufficient safety margin. Our results demonstrate the merit of considering the prior exposure of foodborne pathogens to sub-lethal stresses when validating the storage conditions for leafy greens.