How, when and where the first stars formed are fundamental questions regarding the epoch of Cosmic Dawn. A second order effect in the fluid equations was recently found to make a significant contribution: an offset velocity between gas and dark matter, the so-called streaming velocity. Previous simulations of a limited number of low-mass dark matter haloes suggest that this streaming velocity can delay the formation of the first stars and decrease halo gas fractions and the halo mass function in the low mass regime. However, a systematic exploration of its effects in a large sample of haloes has been lacking until now. In this paper, we present results from a set of cosmological simulations of regions of the Universe with different streaming velocities performed with the moving mesh code AREPO. Our simulations have very high mass resolution, enabling us to accurately resolve minihaloes as small as 105M⊙. We show that in the absence of streaming, the least massive halo that contains cold gas has a mass Mhalo,min=5×105M⊙, but that cooling only becomes efficient in a majority of haloes for halo masses greater than Mhalo,50%=1.6×106M⊙. In regions with non-zero streaming velocities, Mhalo,min and Mhalo,50% both increase significantly, by around a factor of a few for each one sigma increase in the value of the local streaming velocity. As a result, in regions with streaming velocities vstream≥3σrms, cooling of gas in minihaloes is completely suppressed, implying that the first stars in these regions form within atomic cooling haloes.