Cobalt-free oxide electrode materials have received increasing attention due to the interest in replacing critical raw materials in clean energy technologies. Among other compositions, La0.6Sr0.4Fe0.8Cu0.2O3-δ (LSFCu)-based perovskites were proposed in the past for Solid Oxide Fuel Cell (SOFCs) applications due to their mixed ionic-electronic conductivity and low polarisation resistance. In this work, novel LSFCu-based compositions have been explored for their use as oxygen electrodes in SOFC and Solid Oxide Electrolysis Cells (SOECs). Single-phase LSFCu and fluorite-perovskite nanocomposites with (La,Ce)O2-δ-(La,Ce)0.6Sr0.4Fe0.8Cu0.2O3-δ composition were studied, the latter resulting from a one-pot co-synthesis of LSFCu and ceria with intermediate compositions reached by substantial cerium-lanthanum cation intermixing after self-organised phase separation. The best performances were achieved for compositionally complex nanocomposites based on 20% and 50% ceria with full-cell power densities of 1.15 and 1.26 W·cm−2 in SOFC mode (0.7 V), and current densities of 1.41 and 1.75 A·cm−2 in SOEC mode (1.3 V), at 800 °C. Durability tests performed in SOFC mode at 800 °C under high current densities (1 A·cm−2) during nearly 900 h confirmed the benefits of optimal ceria incorporation, showing a remarkable reduction (7x lower) in the degradation rate compared to single-phase LSFCu. This work presents a straightforward approach to fabricating cobalt-free oxygen electrodes for SOC technology, opening a new avenue for developing highly complex composition (high entropy) self-organised nanocomposites.