The first stars, galaxies, star clusters, and direct-collapse black holes are expected to have formed in low-mass (∼105-109 M⊙) haloes at Cosmic Dawn (z ∼10-30) under conditions of efficient gas cooling, leading to gas collapse towards the centre of the halo. The halo mass cooling threshold has been analysed by several authors using both analytical models and numerical simulations, with differing results. Since the halo number density is a sensitive function of the halo mass, an accurate model of the cooling threshold is needed for (semi-)analytical models of star formation at Cosmic Dawn. In this paper, the cooling threshold mass is calculated (semi-)analytically, considering the effects of H2-cooling and formation (in the gas phase and on dust grains), cooling by atomic metals, Lyman-α cooling, photodissociation of H2 by Lyman-Werner photons (including self-shielding by H2), photodetachment of H- by infrared photons, photoevaporation by ionization fronts, and the effect of baryon streaming velocities. We compare the calculations to several high-resolution cosmological simulations, showing excellent agreement. We find that in regions of typical baryon streaming velocities, star formation is possible in haloes of mass ≲ 1-2 × 106 M⊙ for z ≳ 20. By z ≲8, the expected Lyman-Werner background suppresses star formation in all minihaloes below the atomic cooling threshold (Tvir = 104 K). The halo mass cooling threshold increases by another factor of ∼4 following reionization, although this effect is slightly delayed (z ∼4-5) because of effective self-shielding.