The increasing world population and the need to improve quality of life for a large percentage of human beings are the driving forces for the search for sustainable energy production systems, alternative to fossil fuel combustion. Among the various types of alternative energy production technologies, solid oxide fuel cells (SOFCs) operating at intermediate temperatures (400–700 °C) show the advantage of possible use both for stationary and mobile energy production. To reach the goal of reducing the SOFC operating temperature, proton-conducting oxides are gaining wide interest as electrolyte materials. This critical review provides a broad overview of the most recent progresses obtained tailoring the properties of proton-conducting oxides for fuel cell applications, analyzing and comparing the different strategies proposed to match high-proton conductivity with good chemical stability (170 references).