Until quite recently, in almost all papers on crystal nucleation in glass-forming substances, it was assumed that nucleation proceeds in a completely relaxed supercooled liquid and, hence, at constant values of the critical parameters determining the nucleation rate for any given set of temperature, pressure, and composition. Here, we analyze the validity of this hypothesis for a model system by studying nucleation in a lithium silicate glass treated for very long times (up to 250 days) in deeply supercooled states, reaching 60 K below the laboratory glass transition temperature, Tg. At all temperatures in the considered range, T < Tg, we observed an enormous difference between the experimental number of nucleated crystals, N(t), and its theoretically expected value computed by assuming the metastable state of the relaxing glass has been reached. Analyzing the origin of this discrepancy, we confirmed that the key parameters determining the nucleation rates change with time as a result of the glass relaxation process. Finally, we demonstrate that, for temperatures below 683 K, this particular glass almost fully crystallizes prior to reaching the ultimate steady-state nucleation regime (e.g., at 663 K, it would take 176 years for the glass to reach 99% crystallization, while 2600 years would be needed for complete relaxation). This comprehensive study proves that structural relaxation strongly affects crystal nucleation in deeply supercooled states at temperatures well below Tg; hence, this phenomenon has to be accounted for in any crystal nucleation model.