Graphene/Ni-Al layered double hydroxide (LDH) hybrid materials were synthesized by a hydrothermal reaction. Hexagonal Ni-Al LDH particles nucleated and grew on graphene sheets, thus preventing restacking of the graphene sheets and aggregation of the Ni-Al LDH nanoparticles upon drying. Electrode made from the graphene/Ni-Al LDH hybrid materials showed a substantial improvement in electrochemical capacitance relative to those made with pure Ni-Al LDH nanoparticles. In addition, the graphene/Ni-Al LDH hybrid composite materials showed remarkable stability after 4000 cycles with over 100% capacitance retention. These materials are thus very promising for use in electrochemical capacitor electrodes.