Zr0.84Y0.16O1.92−La0.8Sr0.2Cr0.5Fe0.5O3−δ (YSZ-LSCrF) dual-phase composite hollow fiber membranes were prepared by a combined phase-inversion and sintering method. The shell surface of the hollow fiber membrane was modified with Ce0.8Sm0.2O1.9 (SDC) via a drop−coating method. As the rate of oxygen permeation of the unmodified membrane is partly controlled by the surface exchange kinetics, coating of a porous layer of SDC on the shell side (oxygen reduction side) of the hollow fiber membrane was found to improve its oxygen permeability. Rate enhancements up to 113 and 48% were observed, yielding a maximum oxygen flux of 0.32 and 4.53 mL min−1 cm−2 under air/helium and air/CO gradients at 950 °C, respectively. Excess coating of SDC was found to induce significant gas phase transport limitations and hence lower the rate of oxygen permeation. A model was proposed to calculate the length of triple phase boundaries (TPBs) for the coated dual-phase composite membrane and to explain the effect of coating on the oxygen permeability.