The lithium-ir battery is one of the most promising technologies among various electrochemical energy storage systems. We demonstrate that a novel air electrode consisting of an unusual hierarchical arrangement of functionalized graphene sheets (with no catalyst) delivers an exceptionally high capacity of 15000 mAh/g in lithium-O-2 batteries which is the highest value ever reported in this field. This excellent performance is attributed to the unique bimodal porous structure of the electrode which consists of microporous channels facilitating rapid O-2 diffusion while the highly connected nanoscale pores provide a high density of reactive sites for Li-O-2 reactions. Further, we show that the defects and functional groups on graphene favor the formation of isolated nanosized Li2O2 particles and help prevent air blocking in the air electrode. The hierarchically ordered porous structure in bulk graphene enables its practical applications by promoting accessibility to most graphene sheets in this structure.