This paper reports an experimental investigation focused on nano-enhanced phase change materials (NEPCM). Two different types of phase change materials (RT28 HC and RT26) with relatively low thermal conductivity and reasonable volumetric specific heat capacity were utilized as the base for NEPCMs with four types of nanoparticles (CuO, ZnO, Ag, and graphene). The novel four-phase preparation procedure was thoroughly presented together with a description of the measurement technology which was used for the examination of NEPCM thermal constants. The experimental results revealed that in most cases the thermal constants of samples were improved, such as thermal conductivity and volumetric specific heat capacity in a range of about 4% to 21% and 5% to 33%, respectively. In some cases, significant degradation of certain thermal constants was detected, such as in the case of the Graphene/RT26 nanocomposite. The possible nanomaterial selection strategies also discussed taking into account the economic aspects and experimental results related to the thermal constants. The results revealed that the selection of nanomaterials should be carefully considered with respect to the specific application since it is possible to manipulate the thermo-physical properties of the NEPCM as a unique combination of nanomaterial and PCM.