Novel crystalline covalent organic polymers (COPs) were constructed by reacting 1,4-diaminoanthraquinone with 1,3,5-triformylphloroglucinol or tris(4-formylphenyl)amine (TPDA or TADA). After they were covalently bonded to amine-functionalized graphene oxides, the resulting mesoporous COPs@graphene composites demonstrated efficient capacitance storage performance in both alkaline and acidic media. In particular, the as-synthesized TPDA@graphene displayed a reversible specific capacitance of 522 F g⁻¹ in a 6.0 mol L⁻¹ aqueous KOH electrolyte, superior to the previously reported COPs with inconspicuous capacitance storage properties in alkaline media. Its specific capacitance also reached 390 F g⁻¹ in 2.0 mol L⁻¹ H₂SO₄. The impressive capacitance storage properties of this composite can be ascribed to its unique structure with abundant pendulous anthraquinone redox groups and better electrical conductivity enhanced by the coupled graphenes.