The support material can play an important role in oxidation catalysis, notably for CO oxidation. Here, we study two materials of the Brownmillerite family, CaFeO2.5 and SrFeO2.5, as one example of a stoichiometric phase (CaFeO2.5, CFO) and one existing in different modifications (SrFeO2.75, SrFeO2.875 and SrFeO3, SFO). The two materials are synthesized using two synthesis methods, one bottom-up approach via a complexation route and one top-down method (electric arc fusion), allowing to study the impact of the specific surface area on the oxygen mobility and catalytic performance. CO oxidation on 18O-exchanged materials shows that oxygen from SFO participates in the reaction as soon as the reaction starts, while for CFO, this onset takes place 185 °C after reaction onset. This indicates that the structure of the support material has an impact on the catalytic performance. We report here on significant differences in the catalytic activity linked to long-term stability of CFO and SFO, which is an important parameter not only for possible applications, but equally to better understand the mechanism of the catalytic activity itself.