Ni cermet anodes pose considerable problems for SOFC operation in natural gas fuels, particularly with regard to carbon deposition due to hydrocarbon cracking. Oxide anodes offer a good alternative, particularly if a material combining good electronic and ionic transport properties can be utilised. In our search for alternative anode materials, we have investigated fluorite-based systems containing reducible early transition metal dopants. The extent of phase stability has been investigated by solid-state chemical techniques and electrical properties have been investigated by ac impedance techniques as a function of both temperature and oxygen partial pressure. The Nb-Zr-Y-O system has been found to provide a good model system exhibiting reasonable electrical properties. Niobium pentoxide exhibits a wide range of solid solubility in the yttria-zirconia cubic fluorite system and the fluorite structure is retained under reducing conditions. Electronic conductivity increases as niobium concentration increases; however oxide-ionic conductivity decreases with extent of niobium substitution. The defect chemistry of this system, which determines the electrical properties, is dominated by the high concentration of oxide vacancies necessary to stabilise the cubic structure, hence electronic conductivity exhibits a p(O-2)(-1/4) dependence on oxygen partial pressure.