In this study, macroscopic graphene-wrapped melamine foams (MF-G) were fabricated by an MF-templated layer-by-layer (LBL) assembly using graphene oxide as building blocks, followed by solution-processed reduction. By concisely duplicating sponge-like, highly ordered three-dimensional architectures from MF, the resulting MF-G with an interconnected graphene-based scaffold and tunable nanostructure was explored as compressible, robust electrodes for efficient energy storage. A thin layer of pseudocapacitive polypyrrole (PPy) was then attached and uniformly coated on MF-G, resulting in a well-defined core–double-shell configuration of the MF-G-PPy ternary composite sponges. The as-assembled devices exhibited enhancement of supercapacitor performance, with a high specific capacitance of 427 F·g^-1 under a compressive strain of 75% and an excellent cycling stability with only 18% degradation after 5, 000 charge–discharge cycles. Besides, the MF-G-PPy electrode maintained stable capacitance up to 100 compression–release cycles, with a compressive strain of 75%. These encouraging results thus provide a new route towards the low-cost, easily scalable fabrication of lightweight and deformation-tolerant electrodes.