Based on a novel perovskite solid electrolyte, BaCeO3:Gd (10 mol%), hydrogen-oxygen fuel cells have been constructed and operated, giving open circuit voltages of 1.2 to 1.0 V at 600 and 800-degrees-C respectively. Under load, current densities varied inversely with electrolyte thickness, the highest values at a terminal voltage of 700 mV being 25 and 105 mA cm-2 at 600 and 800-degrees-C respectively. Fuel cells based on this material gave current-voltage performances significantly better than those of a comparable cell based on ceria-gadolinia (20 mol%). The stability of BaCeO3:Gd was demonstrated by operation of a fuel cell under load for 1000 h with no degradation of performance. Measurement of the water content of exhaust gases indicated that the ionic transport mechanism varied from purely protonic, at 600-degrees-C or below, to predominantly oxide ion above 900-degrees-C. The compound is judged to be a good candidate solid electrolyte for fuel cells operating in the temperature range 600 to 800-degrees-C.