The practical use of Ba0.5Sr0.5Co0.8Fe0.2O3-δ (BSCF) prototypical oxygen-transport membrane for air separation is currently hampered by the decomposition of the cubic perovskite into a variant with hexagonal stacking at intermediate temperatures of ≤850 °C, which impairs the oxygen transport. Here, we report the development of a W-doped BSCF composite that contains Fe-rich single perovskite (SP) and W-rich double perovskite (DP) phases with different crystallographic parameters. In contrast to BSCF, the BSCFW SP/DP composite maintains its cubic structure at 800 °C for 200 h, demonstrating its structural stability at intermediate temperatures. We use X-ray diffraction, scanning electron microscopy, and high-resolution transmission electron microscopy to show that the enhanced phase stability of the composite is associated with a temperature-induced SP-DP dynamic interaction, which involves W and Fe interdiffusion between the SP and DP phases, dynamically adjusting the chemical composition and limiting structural distortion and new phase formation. The composite exhibits a stable permeation performance in the oxygen-transport membrane during over 150 h operation at 800 and 700 °C, confirming the potential of intermediate-temperature oxygen-transport membranes for air separation and providing insight for designing thermally stable composite oxides.