Solid oxide fuel cells having improved low-temperature operation are disclosed. In one embodiment, an interfacial layer of terbia-stabilized zirconia is located between the air electrode and electrolyte of the solid oxide fuel cell. The interfacial layer provides a barrier which controls interaction between the air electrode and electrolyte. The interfacial layer also reduces polarization loss through the reduction of the air electrode/electrolyte interfacial electrical resistance. In another embodiment, the solid oxide fuel cell comprises a scandia-stabilized zirconia electrolyte having high electrical conductivity. The scandia-stabilized zirconia electrolyte may be provided as a very thin layer in order to reduce resistance. The scandia-stabilized electrolyte is preferably used in combination with the terbia-stabilized interfacial layer. The solid oxide fuel cells are operable over wider temperature ranges and wider temperature gradients in comparison with conventional fuel cells.