Storage of light is the underlying mechanism of quantum memories for photons in atomic ensembles. Alkali vapor ensembles were shown to be ideal for this task, combining the relative simplicity of a thermal system with high optical depths and long memory lifetimes. Up until now, spin-exchange collisions between the alkali atoms have been the dominant relaxation mechanism, limiting the reported memory lifetimes to a few milliseconds. Here we develop a new scheme for storage of light, which is immune to spin-exchange relaxation. We implement our scheme with cesium atoms and demonstrate a record 100-millisecond storage lifetime. Our scheme maps the photonic state onto the Bloch sphere of the alkali spin, paving the way to future orders-of-magnitude improvement utilizing rare-gas hyper-polarization.