Global warming and environmental awareness in general have increased the research into thermal energy storage fields. Phase-change materials (PCMs) are efficient in storing thermal energy because of their high latent heat during the phase change. As the phase change is often based on the melting of the PCM, they need to be encapsulated, for example, by dispersing the PCM to a polymer matrix. In this study, the feasibility of the use of paraffin–natural rubber composites in applications requiring both the good ability to store heat energy and good vibration-damping properties is studied. This includes studies on PCM concentration and the microencapsulation of the PCM. It was found that the heat storage capacity increases with increasing PCM content, although the theoretical maximum capacity is not achieved because the PCM is released during vulcanization and the paraffin blooms. In addition, the loss factor was found to be increased at elevated temperatures, indicating improved damping properties. The encapsulation of PCM is found to have a positive influence on the heat storage capacity and the mechanical and damping properties of the rubber compound.