The oxygen surface exchange kinetics of mixed-conducting perovskite La0.58Sr0.4Co0.2Fe0.8O3 d (LSCF) ceramics coated with a porous nano-particulate layer of either gadolinea (Gd2O3), ceria (CeO2) or 20 mol% Gd-doped ceria (GCO) was determined by electrical conductivity relaxation (ECR). The measurements were performed in the temperature range 700–900 C, following pO2-step changes between 0.2 and 0.4 atm. The apparent value of the surface exchange coefficient, kchem, is found to vary with the loading amount and ionic conductivity of the coated phase whilst, as expected, the chemical diffusion coefficient Dchem remains invariant with the applied coating. Partial coverage of the LSCF surface with non-ionic conductive Gd2O3 or CeO2 lowers the value of kchem relative to that observed for bare LSCF, which is attributed to surface blocking effects. In contrast, partial coverage of LSCF with GCO electrolyte particles enhances the apparent value of kchem up to a factor of 6 compared to bare LSCF. The data of pulse isotope exchange (PIE) measurements show that the surface exchange reaction on bare LSCF is predominantly limited by dissociative adsorption of O2. Different mechanisms for the improved oxygen surface exchange kinetics after partially covering the LSCF surface with GCO are discussed.