Phase change material emulsions (PCMEs) were largely investigated as potential working fluids for various applications as in HVAC systems, solar thermal storage, and heat transfer. They basically contain water and phase change materials, possess much larger energy storage capacity than currently used chilled water based systems and exploit higher thermal conductivity than bulk PCM reservoirs. Main barriers to their application are the difficulty in maintaining emulsion stability and the undercooling effect. In this work, a new solvent-assisted route was developed to produce nano-emulsions of commercial paraffin waxes in water. Concentrations from 2 to 10 wt% were obtained starting from two commercial paraffin waxes, with nominal melting temperatures around 55 degrees C and 70 degrees C. The droplet dimensions were verified and resulted below 100 nm for lower concentrations and around 180-220 nm for 10 wt%. The stability of emulsions was verified by long-term tests. An undercooling effect was verified and strongly reduced by testing some nucleating agents (a paraffin melting at 70 degrees C in the paraffin melting at 55 degrees C or a carbon nanostructure, single wall carbon nanohorns). The heat of melting was lower than expected, probably due to PCM molecules on the surface of the nanoparticles anchored to the surfactant. However, calculating the thermal capacity of PCMEs with respect to pure water, a gain up to 40% for operating temperatures close to PCM melting temperature was estimated. Optical properties of single wall carbon nanohoms/paraffin composites were also measured.