Complex transition-metal oxides are important functional materials in areas such as energy and information storage. The cubic ABOb>3b> perovskite is an archetypal example of this class, formed by the occupation of small octahedral B-sites within an AOb>3b> network defined by larger A cations. We show that introduction of chemically mismatched octahedral cations into a cubic perovskite oxide parent phase modifies structure and composition beyond the unit cell length scale on the B sublattice alone. This affords an endotaxial nanocomposite of two cubic perovskite phases with distinct properties. These locally B-site cation-ordered and -disordered phases share a single AOb>3b> network and have enhanced stability against the formation of a competing hexagonal structure over the single-phase parent. Synergic integration of the distinct properties of these phases by the coherent interfaces of the composite produces solid oxide fuel cell cathode performance superior to that expected from the component phases in isolation.