Though cryogenic storage is presumed to provide nearly infinite longevity to cells, the actual shelf life achieved under ultra-cold temperatures has not been addressed theoretically or empirically. Here, we report measurable changes in germination of dried seeds stored under liquid nitrogen conditions for >10 years. There was considerable variability in the extent of deterioration among species and accessions within a species. Aging time courses for lettuce seeds stored at temperatures between 50 and -196 degrees C were fit to a form of the Avrami equation to determine rate coefficients and predict half-life of accessions. A reduction in the temperature dependency on aging rate, determined as a break in the Arrhenius plot, occurred at about -15 degrees C, and this resulted in faster deterioration than anticipated from extrapolation of kinetics measured at higher temperatures. The break in Arrhenius behavior occurred at temperatures in between the glass transition temperature (28 degrees C) and the Kauzmann temperature (-42 degrees C) and also coincided with a major triacylglycerol phase change (-40 to -7 degrees C). In spite of the faster than anticipated deterioration, cryogenic storage clearly prolonged shelf life of lettuce seeds with half-lives projected as approximately 500 and approximately 3400 years for fresh lettuce seeds stored in the vapor and liquid phases of liquid nitrogen, respectively. The benefit of low temperature storage (-18 or -135 degrees C) on seed longevity was progressively lost if seeds were first stored at 5 degrees C. Collectively, these results demonstrate that lowering storage temperature progressively increases longevity of seeds. However, cryogenic temperatures were not sufficient to stop deterioration, especially if initial stages of aging were allowed to progress at higher storage temperatures. This work contributes to reliable assessments of the potential benefit and cost of different genebanking strategies.