Interactions between the active components with the support are one of the fundamentally factors in determining the catalytic performance of a catalyst. In contrast to the comprehensive understanding on the strong metal-support interactions (SMSI) in metal-based catalysts, it remains unclear for the interactions among different oxides in mixed oxide catalysts due to its complexity. In this study, we investigated the interaction between CeO2 and LaFeO3, the two important oxygen storage materials in catalysis area, by tuning the sizes of CeO2 particles and highlight a two-fold effect of the strong oxide-oxide interaction in determining the catalytic activity and selectivity for preferential CO oxidation in hydrogen feeds. It is found that the anchoring of ultra-fine CeO2 particles (<2 nm) at the framework of three-dimensional-ordered macroporous LaFeO3 surface results in a strong interaction between the two oxides that induces the formation of abundant uncoordinated cations and oxygen vacancy at the interface, contributing to the improved oxygen mobility and catalytic activity for CO oxidation. Hydrogen spillover, which is an important evidence of the strong metal-support interactions in precious metal catalysts supported by reducible oxides, is also observed in the H2 reduction process of CeO2/LaFeO3 catalyst due to the presence of ultra-fine CeO2 particles (<2 nm). However, the strong interaction also results in the formation of surface hydroxyl groups, which when combined with the hydrogen spillover reduces the selectivity for preferential CO oxidation. This discovery demonstrates that in hybrid oxide-based catalysts, tuning the interaction among different components is essential for balancing the catalytic activity and selectivity.