We study the constraints that high-redshift structure formation in the universe places on warm dark matter (WDM) dominated cosmological models. We modify the extended Press-Schechter formalism to derive the halo mass function in WDM models. We show that our predictions agree with recent numerical simulations at low redshift over the halo masses of interest. Applying our model to galaxy formation at high redshift, we find that the loss of power on small scales, together with the delayed collapse of low-mass objects, results in strong limits on the root-mean-square velocity dispersion v_rms of the WDM particles at z=0. For fermions decoupling while relativistic, these limits are equivalent to constraints on the mass m_X of the particles. The presence of a 4 billion solar mass black hole at z=5.8, believed to power the quasar SDSS 1044-1215, implies m_X > 0.5 keV (or v_rms < 0.10 km/s), assuming that the quasar is unlensed and radiating at or below the Eddington limit. Reionization by z=5.8 also implies a limit on m_X. If high-redshift galaxies produce ionizing photons with an efficiency similar to their z=3 counterparts, we find m_X > 1.2 keV (or v_rms < 0.03 km/s). However, given the uncertainties in current measurements from the proximity effect of the ionizing background at redshift 3, values of m_X as low as 0.75 keV (v_rms = 0.06 km/s) are not ruled out. The limit weakens further if, instead, the ionizing-photon production efficiency is greater at high z, but this limit will tighten considerably if reionization is shown in the future to have occurred at higher redshifts. WDM models with m_X < 1 keV (v_rms > 0.04 km/s) produce a low-luminosity cutoff in the high-redshift galaxy luminosity function which is directly detectable with the Next Generation Space Telescope (abridged).