Composite phase change materials (C-PCMs) for thermal energy management exploit the reversible phase transition (e.g., melting-solidification) of their one or more low-melting active phases to store and release thermal energy as latent heat. At the same time, the high-melting passive phases can provide additional properties, like form-stability and enhanced thermal conductivity. Fully-metallic composite systems with these features can be obtained from immiscible alloys. In this work, thermodynamic calculations and experimental tests are combined to explore the potential of a set of binary (Al-In, Al-Sn, Al-Bi and Cu-Bi) and ternary (Al-In-Sn and Al-Bi-Sn) immiscible alloys for their use as C-PCMs in a temperature range between 100 and 300 °C. The results show that the combination of the two approaches proved to be necessary to have a full comprehension of the composite system and find the best solution for design requirements, overcoming the time-wasting “trial-and-error” approach and providing high-quality data for simulations.