Electroactive polymers are a new generation of "green" cathode materials for rechargeable lithium batteries. We have developed nanocomposites combining graphene with two promising polymer cathode materials, poly(anthraquinonyl sulfide) and polyimide, to improve their high-rate performance. The polymer-graphene nanocomposites were synthesized through a simple in situ polymerization in the presence of graphene sheets. The highly dispersed graphene sheets in the nanocomposite drastically enhanced the electronic conductivity and allowed the electrochemical activity of the polymer cathode to be efficiently utilized. This allows for ultrafast charging and discharging; the composite can deliver more than 100 mAh/g within just a few seconds.