We extend the density functional approach to the statistical mechanics of inhomogeneous fluids to calculate the rate of heterogeneous nucleation of the gas-to-liquid transition by a planar solid substrate. Comparison with classical nucleation theory (extended to incorporate the line tension that results from three-phase contact) reveals the inadequacy of the latter approaches as the spinodal is approached. Wetting and drying transitions have a large effect on the usefulness of classical theory. Free energies of formation for critical heterogeneous nuclei and their shapes and density profiles are calculated from density functional theory.