We present a detailed study of the lifetime of optical spectral holes due to population storage in Zeeman sublevels of Nd3+:Y2SiO5. The lifetime is measured as a function of magnetic field strength and orientation, temperature, and Nd3+ doping concentration. At the lowest temperature of 3 K we find a general trend where the lifetime is short at low field strengths, then increases to a maximum lifetime at a few hundred mT, and then finally decays rapidly for high field strengths. This behavior can be modeled with a relaxation rate dominated by Nd3+−Nd3+ cross relaxation at low fields and spin lattice relaxation at high magnetic fields. The maximum lifetime depends strongly on both the field strength and orientation, due to the competition between these processes and their different angular dependencies. The cross relaxation limits the maximum lifetime for concentrations as low as 30 ppm of Nd3+ ions. By decreasing the concentration to less than 1 ppm we could completely eliminate the cross relaxation, reaching a lifetime of 3.8 s at 3 K. At higher temperatures the spectral hole lifetime is limited by the magnetic-field-independent Raman and Orbach processes. In addition we show that the cross relaxation rate can be strongly reduced by creating spectrally large holes of the order of the optical inhomogeneous broadening. Our results are important for the development and design of new rare-earth-ion doped crystals for quantum information processing and narrow-band spectral filtering for biological tissue imaging.