Substrates effect is observed on the suppression of the phonon sideband from nitrogen vacancy (NV) centers in 50nm diamond nanocrystals at cryogenic temperatures. As a quantitative parameter of the population of phonon sidebands, the Debye-Waller factor is estimated from fluorescence spectra on glass, silicon, and silica-on-silicon substrates. Fluorescence spectra of negatively charged NV centers in nanodiamonds on silica-on-silicon substrates have average and maximum Debye-Waller factors of 12.7% (which is about six times greater than that of samples on glass substrates) and 19.3%, respectively. This effect is expected to be very important for future applications of NV centers in quantum information science and nanosensing. (C) 2012 Optical Society of America