Cryopreserved semen is routinely shipped in liquid nitrogen. Dry ice could serve as an alternative coolant, however, frozen storage above liquid nitrogen temperatures (LN2, −196 °C) may negatively affect shelf-life and cryosurvival. In this study, we determined critical temperatures for storage of cryopreserved stallion sperm. We evaluated: (i) effects of cooling samples to different subzero temperatures (−10 °C to −80 °C) prior to storing in LN2, (ii) stability at different storage temperatures (i.e., in LN2, dry ice, −80 °C and −20 °C freezers, 5 °C refrigerator), and (iii) sperm cryosurvival during storage on dry ice (i.e., when kept below −70 °C and during warming). Furthermore, (iv) we analyzed if addition of synthetic polymers (PVP-40, Ficoll-70) modulates ice crystallization kinetics and improves stability of cryopreserved specimens. Sperm motility and membrane intactness were taken as measures of cryosurvival, and an artificial insemination trial was performed to confirm fertilizing capacity. We found that adding PVP-40 or Ficoll-70 to formulations containing glycerol reduced ice crystal sizes and growth during annealing. Post-thaw sperm viability data indicated that samples need to be cooled below −40 °C before they can be safely plunged and stored in LN2. No negative effects of relocating specimens from dry ice to LN2 and vice versa became apparent. However, sample warming above −50 °C during transport in dry ice should be avoided to ensure preservation of viability and fertility. Moreover, addition of PVP-40 or Ficoll-70 was found to increase sperm cryosurvival, especially under non-ideal storage conditions where ice recrystallization may occur.