For thermophysical energy storage with phase change materials (PCMs), the power capacity is often limited by the low PCM thermal conductivity (κPCM). Though dispersing high-thermal conductivity nanotubes and graphene flakes increases κPCM, the enhancement is limited by interface thermal resistance between the nanofillers, among other factors such as detrimental surface scattering of phonons. Here, we demonstrate that embedding continuous ultrathin-graphite foams (UGFs) with volume fractions as low as 0.8-1.2 vol% in a PCM can increase κPCM by up to 18 times, with negligible change in the PCM melting temperature or mass specific heat of fusion. The increase in κPCM, thermal cycling stability, and applicability to a diverse range of PCMs suggests that UGF composites are a promising route to achieving the high power capacity targets of a number of thermal storage applications, including building and vehicle heating and cooling, solar thermal harvesting, and thermal management of electrochemical energy storage and electronic devices.