Sugar alcohols (SA) are attractive phase change materials for long-term thermal energy storage (TES) applications at low-to-medium temperatures, as i.e. solar seasonal energy storage. Most of them undergo severe undercooling, thus allowing energy storage at temperatures far below the melting point with thermal losses reduction. Besides, some of them could provide very high volumetric energy density at affordable cost. However, sugar alcohols with high latent heat of fusion often exhibit melting temperatures above 100 °C. The objective of this work was to found out new sugar alcohol eutectic mixtures that display lower temperatures without significant reduction of the latent heat. A comprehensive analysis of SA relevant properties for TES has been carried out in order to select the most appropriate single SA for mixtures analysis. Sixteen SA-based binary systems have been investigated. Their corresponding phase diagrams have been experimentally and theoretically established. Four eutectic mixtures with potential for long-term TES at temperature around 80 °C have been identified. They are: 1) adonitol-erythritol at 30 mol% of erythritol, with melting temperature of 87 °C and latent heat of fusion of 254 J/g; 2) arabitol-erythritol at 40 mol% of erythritol, with melting temperature of 86 °C and latent heat of fusion of 225 J/g; 3) xylitol-erythritol at 36 mol% of erythritol, with melting temperature of 82 °C and latent heat of fusion of 270 J/g; and 4) arabitol-xylitol at 56 mol% of xylitol, with melting temperature of 77 °C and latent heat of fusion of 243 J/g.