The size of the smallest dark matter collapsed structures, or protohalos, is set by the temperature at which dark matter particles fall out of kinetic equilibrium. The process of kinetic decoupling involves elastic scattering of dark matter off of Standard Model particles in the early universe, and the relevant cross section is thus closely related to the cross section for dark matter scattering off of nuclei (direct detection) but also, via crossing symmetries, for dark matter pair production at colliders and for pair annihilation. In this study, we employ an effective-field-theoretic approach to calculate constraints on the kinetic decoupling temperature, and thus on the size of the smallest protohalos, from a variety of direct, indirect and collider probes of particle dark matter.