Aiming to clarify the grain boundary conductance mechanism of CeO2/BaCeO3 based electrolytes suitable for solid oxide fuel cells (SOFCs), Sm, Bi co-doping CeO2/BaCeO3 (80 wt.% Ce0.8Sm0.1Bi0.1O2-δ - 20 wt.% BaCe0.8Sm0.1Bi0.1O3-δ, BiSDC-BCSBi) electrolytes with ultra-fine grained (110-220 nm) and micron (1-1.8 μm) structures were prepared by the two step sintering and conventional sintering method, respectively. Both electrolytes have pure phases corresponding to CeO2 and BaCeO3 without other purities. In the ultra-fine grained structure, apparent grain boundary conductivities measured at 350 oC and 400 oC are 1-2 orders of magnitude higher than micron structures, thus resulting in dramatically enhanced electrical performances. This grain boundary effect can be attributed to two aspects. One is the decrease of space charge potential Δφ(0) (0.165 V for ultrafine-fine grained ones, 0.396 V for micron ones). The other is the dilution of impurities (the impurity blocking term ω/dg is 0.94 for ultrafine-fine grained ones, and 0.53 for micron ones). In the ultra-fine grained electrolytes, no extra electronic conduction is introduced, and the ion migration number of O2- is higher than that of H+. Finally, the ultra-fine grained BiSDC-BCSBi electrolytes maintain a good long-term stability in the operating condition of SOFCs at 600 oC for 100 h.