This critical review presents an overview of the various classes of oxide materials exhibiting fast oxide-ion or proton conductivity for use as solid electrolytes in clean energy applications such as solid oxide fuel cells. Emphasis is placed on the relationship between structural and mechanistic features of the crystalline materials and their ion conduction properties. After describing well-established classes such as fluorite- and perovskite-based oxides, new materials and structure-types are presented. These include a variety of molybdate, gallate, apatite silicate/germanate and niobate systems, many of which contain flexible structural networks, and exhibit different defect properties and transport mechanisms to the conventional materials. It is concluded that the rich chemistry of these important systems provides diverse possibilities for developing superior ionic conductors for use as solid electrolytes in fuel cells and related applications. In most cases, a greater atomic-level understanding of the structures, defects and conduction mechanisms is achieved through a combination of experimental and computational techniques (217 references).