We investigate the power spectrum of Non-Cold Dark Matter (NCDM) produced in a state out of thermal equilibrium. We consider dark matter production from the decay of scalar condensates (inflaton, moduli), the decay of thermalized and non-thermalized particles, and from thermal and non-thermal freeze-in. For each case, we compute the NCDM phase space distribution and the linear matter power spectrum, which features a cutoff analogous to that for Warm Dark Matter (WDM). This scale is solely determined by the equation of state of NCDM. We propose a mapping procedure that translates the WDM Lyman-$\alpha$ mass bound to NCDM scenarios. This procedure does not require expensive ad hoc numerical computations of the non-linear matter power spectrum. By applying it, we obtain bounds on several NCDM possibilities, ranging from $m_{\rm DM}>$ EeV for DM production from inflaton decay with a low reheating temperature, to sub-keV values for non-thermal freeze-in. We discuss the phenomenological implications of these results for specific examples which include strongly-stabilized and non-stabilized supersymmetric moduli, gravitino production from inflaton decay, $Z'$ and spin-2 mediated freeze-in, and non-supersymmetric spin-3/2 DM.