We show that cold dark matter particles interacting through a Yukawa potential could naturally explain the recently observed cores in dwarf galaxies without affecting the dynamics of objects with a much larger velocity dispersion, such as clusters of galaxies. The velocity dependence of the associated cross-section as well as the possible exothermic nature of the interaction alleviates earlier concerns about strongly interacting dark matter. Dark matter evaporation in low-mass objects might explain the observed deficit of satellite galaxies in the Milky Way halo and have important implications for the first galaxies and reionization.