Heterostructured composite ceria electrolytes have been shown to accelerate the oxygen reduction activity and provide a new approach to improve solid oxide fuel cell (SOFC) performance. In this study, barium carbonate was added to gadolinium-doped ceria, GdCeO (GDC) electrolyte to improve the electrochemical performance of intermediate-temperature SOFCs. The heterostructured electrolyte was formed by the addition of 5 wt % BaCO to a GDC electrolyte, resulting in a reaction during sintering that formed well-dispersed BaCeGdO (BCG) throughout the electrolyte. The resulting material was tested as an electrolyte using LaSrCoFeO as a cathode, resulting in a dramatic reduction to the polarization resistance of more than half the value (600 and 700 °C, the resistance was reduced from 2.49 and 0.23 Ω cm to 1.21 and 0.12 Ω cm) obtained by using pure GDC as an electrolyte. Furthermore, full cell SOFC tests employing the heterostructured electrolyte conducted during overextended durations indicated that the BCG phase in the 5BCG-GDC electrolyte was stable in an air atmosphere with no observed reactions with residual CO. This approach of tailoring surface reactivity by tailoring the composition and structure of the electrolyte as opposed to electrode materials provides an alternative method to improve fuel cell performance.