In this study, the influence of long-term annealing at intermediate temperatures on oxygen transport of Ba0.5Sr0.5Co0.8Fe0.2O3 d (BSCF) and 3 mol% Zr-doped BSCF (BSCF-Z3) ceramics with different grain sizes was studied by means of in situ electrical conductivity relaxation (ECR) measurements. Ceramics with different grain sizes in the range of 3–80 mm were obtained by varying the temperature and dwell time during sintering. For both compositions, the apparent values of the chemical diffusion coefficient Dchem and surface exchange coefficient kchem extracted from the data of ECR measurements are found to decrease with the time of annealing. The strongly correlated decreases in Dchem and kchem, being greater in magnitude at a lower grain size and temperature, are observed significantly more pronounced for BSCF than for BSCF-Z3. The results from microstructural analysis provide a clear rationale for the observations from ECR. High-resolution transmission electron microscopy (TEM) images recorded before and after annealing under pure oxygen at 700 C for 13 d show excessive formation of hexagonal and plate-like lamellar precipitates at the grain boundaries and in the interior of grains of BSCF ceramics during the annealing process, whilst secondary phase formation is restricted solely to the grain boundary regions in BSCF-Z3. The possible importance of grain boundaries in determining the oxygen surface exchange kinetics is emphasized.