Efficient energy storage systems based on lithium-ion batteries represent a critical technology across many sectors including consumer electronics, electrified transportation, and a smart grid accommodating intermittent renewable energy sources. Nanostructured electrode materials present compelling opportunities for high-performance lithium-ion batteries, but inherent problems related to the high surface area to volume ratios at the nanometer-scale have impeded their adoption for commercial applications. Here, we demonstrate a materials and processing platform that realizes high-performance nanostructured lithium manganese oxide (nano-LMO) spinel cathodes with conformal graphene coatings as a conductive additive. The resulting nanostructured composite cathodes concurrently resolve multiple problems that have plagued nanoparticle-based lithium-ion battery electrodes including low packing density, high additive content, and poor cycling stability. Moreover, this strategy enhances the intrinsic advantages of nano-LMO, resulting in extraordinary rate capability and low temperature performance. With 75% capacity retention at a 20C cycling rate at room temperature and nearly full capacity retention at -20 degrees C, this work advances lithium-ion battery technology into unprecedented regimes of operation.