The increase in energy demand and the need for lower CO2 emissions have increased the importance of natural gas as the cleanest fossil fuel in the energy market. Natural gas is mainly transported using pipelines or as liquefied natural gas (LNG). LNG is stored and transported in cryogenic storage tankers, where a part of the LNG evaporates, generating boil-off gas (BOG). The BOG is used normally as fuel for propulsion engines, but at low navigation speed, it is more than the engines’ fuel needs, and the excess quantity is either burnt or reliquefied. Existing technologies for on-board reliquefaction consume a large amount of energy and are costly, which arises the need for new concepts of reliquefaction technologies. The new proposed system operates on two modes; the first is the charging mode in which cold energy is stored when the LNG is evaporated to supply the LNG carrier propulsion system at high speed. The second is the discharging mode, in which the stored cold energy is used to condense the excess BOG at low navigation speed. The novel reliquefaction system utilizes latent or sensible heat storage materials that haven’t been examined before for cryogenic applications. A preliminary energetic assessment for the system is carried out using Aspen HYSYS, Excel and VBA, to study the impact of the variation of the operating conditions on the choice of suitable storage material and its performance. Results showed that low LNG evaporation and high BOG liquefaction pressures offer higher energy storage capacity for all types of thermal energy materials, with better performance for the latent ones. Further investigation on this technology helps in providing a suitable replacement for the costly available reliquefaction systems and avoids the burning of BOG with its consequent high CO2 emissions.