It was recently pointed out that semiannihilating dark matter (DM) may experience a novel temperature evolution dubbed as self-heating. Exothermic semiannihilation converts the DM mass to the kinetic energy. This yields a unique DM temperature evolution, T-chi alpha 1/a, in contrast to T-chi alpha 1/a(2) for free-streaming nonrelativistic particles. Self-heating continues as long as self-scattering sufficiently redistributes the energy of DM particles. In this paper, we study the evolution of cosmological perturbations in self-heating DM. We find that sub-GeV self-heating DM leaves a cutoff on the subgalactic scale of the matter power spectrum when the self-scattering cross section is sigma(self)/m(chi) similar to O(1) cm(2)/g. Then we present a particle physics realization of the self-heating DM scenario. The model is based on recently proposed strongly interacting massive particles with pionlike particles in a QCD-like sector. Pionlike particles semiannihilate into an axionlike particle, which is thermalized with dark radiation. The dark radiation temperature is smaller than the standard model temperature, evading the constraint from the effective number of neutrino degrees of freedom. It is easily realized when the dark sector is populated from the standard model sector through a small coupling