Cellular structures assembled by periodic base cells (PBC) are important carriers of phase change materials (PCMs) in practical applications. The configuration of the PBC and its topology significantly influence the thermal conduction of cellular structures and the thermal storage properties of PCMs. This study develops a framework for multiscale topology optimization of cellular structures, which can first determine the optimal configuration for PBCs and then their optimal density distribution. The optimized topology structure is tree-like, as shown by the hierarchical pores formed by PBCs with varying densities. This hierarchical cellular structure successfully reduces the maximum temperature by 22%, improves the temperature uniformity by 9%, and shortens the melting time by 8% compared to the unoptimized structure. Cellular structures with different topology structures are selective-laser-melting 3D-printed to encapsulate paraffin wax, which experimentally validates that the hierarchical structure can shorten the melting time by 10.4% compared to a uniform structure, even if their porosity is the same. This progress breaks through the conventional concept that the effective thermal conductivity of the cellular structure cannot be modulated once its porosity is fixed and opens up a new idea to improve the melting behavior of PCMs.