The ability of solid oxides to conduct oxide ions has been known for more than a century, and fast oxide-ion conductors (or oxide electrolytes) are now being used for applications ranging from oxide fuel cells to oxygen pumping devices. To be technologically viable, these oxide electrolytes must exhibit high oxide-ion mobility at low operating temperatures. Because of the size and interaction of oxygen ions with the cationic network, high mobility can only be achieved with classes of materials with suitable structural features. So far, high mobility has been observed in only a small number of structural families, such as fluorite, perovskites, intergrowth perovskite/Bi2O2 layers and pyrochlores. Here we report a family of solid oxides based on the parent compound La2Mo2O9 (with a different crystal structure from all known oxide electrolytes) which exhibits fast oxide-ion conducting properties. Like other ionic conductors, this material undergoes a structural transition around 580 degrees C resulting in an increase of conduction by almost two orders of magnitude. Its conductivity is about 6 x 10(-2) S cm(-1) at 800 degrees C, which is comparable to that of stabilized zirconia, the most widely used oxide electrolyte. The structural similarity of La2Mo2O9 with beta-SnWO4 (ref. 14) suggests a structural model for the origin of the oxide-ion conduction. More generally, substitution of a cation that has a lone pair of electrons by a different cation that does not have a lone pair--and which has a higher oxidation state--could be used as an original way to design other oxide-ion conductors.