We report the design of all-solid-state asymmetric supercapacitors based on free-standing carbon nanotube/graphene (CNTG) and Mn3O4 nanoparticles/graphene (MG) paper electrodes with a polymer gel electrolyte of potassium polyacrylate/KCl. The composite paper electrodes with carbon nanotubes or Mn3O4 nanoparticles uniformly intercalated between the graphene nanosheets exhibited excellent mechanical stability, greatly improved active surface areas, and enhanced ion transportation, in comparison with the pristine graphene paper. The combination of the two paper electrodes with the polymer gel electrolyte endowed our asymmetric supercapacitor of CNTG//MG an increased cell voltage of 1.8 V, a stable cycling performance (capacitance retention of 86.0% after 10 000 continuous charge/discharge cycles), more than 2-fold increase of energy density (32.7 Wh/kg) compared with the symmetric supercapacitors, and importantly a distinguished mechanical flexibility.