Enceladus has all the ingredients to support life in its ocean and is therefore a good place to start looking for extraterrestrial life in our Solar System. To explore Enceladus, a probe is needed that autonomously navigates the extreme, icy and unknown environment. Multiple robotic systems are proposed to explore Enceladus. The concept to be optimised by this research is the Freezing Locomotion Integrated Chain Kinematics (FLICK). This concept uses a track of adhesion links that use state-of-the-art ice locomotion: By melting and freezing the ice with peltier modules integrated into the links, the robot can move over the ice wall. To reach subzero temperatures to freeze the ice, the hot side of the Peltier modules must be cooled. The aim of this research is to optimise the adhesion link design by the replacement of the water cooling system with a Phase Change Material (PCM) cooling system. Utilising the latent heat storage of the PCM, this research provides a solid-state cooling solution. The PCM container was made of aluminium to increase the heat transfer from the Peltier module to the PCM and enable the heat absorbed by the PCM to radiate to the environment. Furthermore, 3 heat fins were used to increase the contact area between the PCM and the container, increasing the available latent heat storage. The cooling performance of various PCMs was tested and the octadecane was found to be the best option, due to its high latent heat capacity and relatively low density. Tests on ice showed ice adhesion with PCM cooling of the Peltier modules was possible. A theoretical model was built to estimate the required octadecane volume to obtain subzero temperatures. 7.457 g of octadecane was integrated into the adhesion link of FLICK. The model of the new link obtained a minimum temperature of -1.1 $\deg$C and subzero cooling time of 45 s, for an ambient temperature of 21 $\deg$C without the presence of ice. Using the designed PCM cooling mechanism, the mass of FLICK's cooling system could be reduced from >1309 g to 375.68 g. However, the system must be built and tested to assess its behaviour and viability. This design assumed Earth conditions. To make the system fit to the cold temperatures and low pressures of Enceladus, the adhesion mechanism should be tested in a cooled vacuum chamber.