At the time of recombination, baryons and photons decoupled and the sound speed in the baryonic fluid dropped from relativistic to the thermal velocities of the hydrogen atoms. This is less than the relative velocities of baryons and dark matter computed via linear perturbation theory, so we infer that there are supersonic coherent flows of the baryons relative to the underlying potential wells created by the dark matter. As a result, the advection of small-scale perturbations (near the baryonic Jeans scale) by large-scale velocity flows is important for the formation of the first baryonic structures. This effect involves a quadratic term in the cosmological perturbation theory equations and hence has not been included in studies based on linear perturbation theory. We show that the relative motion suppresses the abundance of the first bound objects, even if one only investigates dark matter haloes, and leads to qualitative changes in their spatial distribution, such as introducing scale-dependent bias and stochasticity. We discuss the possible observable implications for high-redshift galaxy clustering and reionization.