Warm Dark Matter (WDM) models have recently been resurrected to resolve apparent conflicts of Cold Dark Matter (DM) models with observations. Endowing the DM particles with non-negligible velocities causes free-streaming, which suppresses the primordial power spectrum on small scales. The choice of a root-mean-square velocity dispersionvrms,0∼0.05 km/sat redshiftz=0(corresponding to a particle massmX∼1 keVif the WDM particles are fermions decoupling while relativistic) helps alleviate most, but probably not all, of the small-scale problems faced by CDM. An important side-effect of the particle velocities is the severe decrease in the number of collapsed halos at high redshift. This is caused both by the loss of small-scale power, and by the delay in the collapse of the smallest individual halos (with masses near the effective Jeans mass of the DM). The presence of early halos is required in order (1) to host either early quasars or galaxies that can reionize the universe by redshiftz=5.8,and (2) to allow the growth of the supermassive black hole believed to power the recently discovered quasar SDSS 1044-1215 at this redshift. We quantify these constraints using a modified Press-Schechter formalism, and findvrms,0≲0.04 km/s(ormX≳1 keV). If future observations uncover massive black holes atz≳10,or reveal that reionization occurred atz≳10,this could conclusively rule out WDM models as the solution to the small-scale crisis of the CDM paradigm. ©2001 American Institute of Physics.