A porous graphene paper was prepared by pressing a graphene cryogel, followed by thermal reduction at 220 °C. The cryogel was formed by freeze-drying a solution containing chemically reduced graphene and graphene oxide (CRG/GO). The formed graphene cryogel papers deliver a much higher discharge capacity and rate capability than that from conventional graphene papers fabricated by filtration. These new structures have a discharge capacity higher than 400 mA h g−1 at a current density of 2000 mA g−1 in sharp contrast to 229 mA h g−1 at 50 mA g−1 obtained from conventional graphene papers. These greatly improved electrochemical properties may be attributed to the porous structure and the concomitant high surface area. The mechanical properties may be tuned with the CRG/GO ratio. At a CRG/GO mass ratio of 2:1 the graphene paper has a Young's modulus nearly 9 times greater than an equivalent paper made from pure GO.