If the Universe's energy density was dominated by a fast-rolling scalar field while the radiation bath was hot enough to thermally produce dark matter, then dark matter with larger-than-canonical annihilation cross sections can generate the observed dark matter relic abundance. To further constrain these scenarios, we investigate the evolution of small-scale density perturbations during such a period of kination. We determine that once a perturbation mode enters the horizon during kination, the gravitational potential drops sharply and begins to oscillate and decay. Nevertheless, dark matter density perturbations that enter the horizon during an era of kination grow linearly with the scale factor prior to the onset of radiation domination. Consequently, kination leaves a distinctive imprint on the matter power spectrum: scales that enter the horizon during kination have enhanced inhomogeneity. We also consider how matter density perturbations evolve when the dominant component of the Universe has a generic equation-of-state parameter $w$. We find that matter density perturbations do not grow if they enter the horizon when ${0< w < 1/3}$. If matter density perturbations enter the horizon when ${w > 1/3}$, their growth is faster than the logarithmic growth experienced during radiation domination. The resulting boost to the small-scale matter power spectrum leads to the formation of enhanced substructure, which effectively increases the dark matter annihilation rate and could make thermal dark matter production during an era of kination incompatible with observations.