We formulate a new class of primordial perturbations called $\textit{kinetic isocurvature perturbations}$, where the mass density of dark matter is constant relative to the photon number density while the kinetic energy of dark matter fluctuates in space. Such perturbations naturally arise in scenarios where a nonrelativistic heavy field decays into relativistic dark matter particles with a spatially modulated rate. As dark matter cools and becomes nonrelativistic, these fluctuations in kinetic energy leave large-scale density perturbations essentially unaffected and therefore evade the Cosmic Microwave Background bounds on isocurvature perturbations, yet survive as spatial variations in the free-streaming scale, resulting in patch-by-patch variation of the matter power spectrum.