Quality oxide-ion conductors are essential for clean energy applications. Rare-earth-stabilized bismuth sesquioxide, delta-Bi2O3, exhibits a much greater oxide-ion conductivity at high temperatures than commonly used ZrO2- or CeO2-based electrolytes, but it suffers from serious conductivity degradation while annealing at moderate temperatures of similar to 773 K, which is the target temperature for many applications. Here, we demonstrate that a novel set of solute elements for delta-Bi2O3 can significantly enhance the long-term stability at 773 K A pure oxide-ion conductivity of 0.035 S/cm at 773 K remains unchanged during annealing for 100 h, which is five times greater than the best known solid-state oxide materials after long-term annealing. For materials design, we explore a range of chemical spaces using theoretical methods based on first-principles calculations. The order-disorder transition temperature of the anion sublattice, oxygen-ion diffusivity, and solution free energy are used as descriptors. The design concept is verified experimentally.