The shell composition and microstructure of microencapsulated phase-change materials (MPCMs) are of vital significance for achieving high thermal and mechanical properties. Herein, a new type of MPCM with double-walled shells (melamine-formaldehyde (MF) resin/carbon nanotube (CNT)-poly(4-styrenesulfonic acid) sodium (PSS)) was developed through a facile layer-by-layer (LbL) self-assembly technique using prefabricated MF resin-encapsulated n-octadecane as the template. The CNTs were well dispersed and highly interconnected in the shell, which greatly enhanced the temperature response and thermal stability of MPCMs. Furthermore, the incorporation of 3.34 wt% CNTs resulted in an average hardness and Young's modulus of MPCMs, respectively, 3.3 and 1.3 times greater than those of microcapsules without CNTs. The double-walled MPCMs exhibited good potential for application in the field of thermal energy storage.