This paper reports a comprehensive experimental investigation of cement pastes enhanced with Microencapsulated Phase Change Materials (MPCM) for Thermal Energy Storage (TES) purposes. The experimental plan considers three water-to-binder ratios and three MPCM volume fractions, for a total of nine different MPCM paste mixtures. The water-to-binder ratios of the pastes are 0.33, 0.40 and 0.45, which were mixed with a commercial MPCM, namely Nextek 37D® having a melting/solidification temperature of 37 °C, with volume percentage substitutions of 0%, 20% and 40%, respectively. Thermal, physical and mechanical tests were performed to investigate the effect MPCM have on the resulting TES, strengths and conductive properties of the considered mixtures by employing DSC, Hot-Disk, and mechanical tests. The measured latent heat of MPCM was 197.3 J/g and 194.6 J/g for heating and cooling, respectively. The volumetric latent enthalpies for the MPCM-based composites showed an almost constant average of 20–25 MJ/m3 for samples with 20% MPCM and 55–60 MJ/m3 for samples with 40% MPCM, independently of the w/b ratio. Thermal conductivity values measured at 25 and 45 °C ranged between 0.93 and 0.44 W/m × K. MPCM substitution turned out to significantly affect the overall porosity of the composite resulting in a lower thermal conductivity for the MPCM-pastes in comparison to the plain cement matrix. Finally, mechanical tests were conducted that showed a strength loss due to either increasing w/b ratios or for enhanced amounts of MPCM (e.g., up to a 74% and 69% of strength loss were registered for bending and compression, respectively). The thermo-physical and mechanical characterizations were conducted according to an experimental plan that provided a wide set of research results for both sole MPCM and MPCM-cement systems analyzed by SEM, EDS/elemental mapping, contact angle tests, particle size distribution analysis and Mercury Intrusion Porosimetry technique.