Advances in electrochemical devices have primarily been driven by the discovery and development of electrolyte materials. Yet, the ideal electrolyte that combines high ionic conductivity with robust chemical and electrochemical stability remains elusive owing to trade-offs between ionic carrier concentration and conductivity in doped oxides. Here, we demonstrate that heavy Sc doping in soft perovskite oxides overcomes these limitations by creating fast conduction pathways for trapped protons along the ScO6 octahedra network. Specifically, BaSn0.3Sc0.7O3H0.65 and BaTi0.2Sc0.8O3H0.51 achieve high proton concentration and diffusivity, resulting in a total proton conductivity exceeding 0.01 Scm−1 at 300°C. Barium stannate, doped with 70 at% Sc, exhibits enduring chemical stability under humid 0.98 atm CO2 atmosphere for over 360 h, while maintaining a theoretical open-circuit voltage of 1.194 V and a proton conductivity of 0.01 Scm−1 during more than 100 h of continuous fuel cell operation at 300°C. Targeting softer oxides with maximum Sc solubility presents a promising route for developing fast, stable proton-conducting solid electrolytes operable at 300°C or lower.