Surfactant or polymer directed self-assembly has been widely investigated to prepare nanostructured metal oxides, semiconductors, and polymers, but this approach is mostly limited to two-phase materials, organic/inorganic hybrids, and nanoparticle or polymer-based nanocomposites. Self-assembled nanostructures from more complex, multiscale, and multiphase building blocks have been investigated with limited success. Here, we demonstrate a ternary self-assembly approach using graphene as fundamental building blocks to construct ordered metal oxide-graphene nanocomposites. A new class of layered nanocomposites is formed containing stable, ordered alternating layers of nanocrystalline metal oxides with graphene or graphene stacks. Alternatively, the graphene or graphene stacks can be incorporated into liquid-crystal-templated nanoporous structures to form high surface area, conductive networks. The self-assembly method can also be used to fabricate free-standing, flexible metal oxide-graphene nanocomposite films and electrodes. We have investigated the Li-ion insertion properties of the self-assembled electrodes for energy storage and show that the SnO2-graphene nanocomposite films can achieve near theoretical specific energy density without significant charge/discharge degradation.