The effects of ZrO2 addition with various particle sizes (1, 3, and 56 Am) and various amounts (0, 1, 3, 5, 7, 9 wt. %) on structure, oxygen permeation, and stability of SrCo0.4Fe0.6O3-delta (SCF) were investigated. XRD and EDX analysis revealed that the dissolution of Zr cation into the B site of SCF phase occurred with the addition of ZrO2, resulting in a lattice expansion of SCF at elevated temperatures. The dissolution amount of Zr in the SCF phase increased with a decrease of ZrO2 particle size and an increase in the amount of ZrO2 added, and, therefore, resulted in a decrease of oxygen permeation flux of the membranes and an increase in their structural stability in a helium atmosphere. This study indicated that adding a certain amount of Zr cation in SCF oxide was an effective route to sustain the structural stability of SCF in low oxygen partial pressure, and the optimum ZrO2 addition was 3 wt.% with a particle size of 1 mum, which greatly improved the structural stability without significantly changing the oxygen permeability of SCF.