Oxides are an important class of materials and are widely used, for example, as supports in heterogeneous catalysis. In a number of industrial catalytic processes, oxide supports actively participate in chemical transformations by releasing lattice oxygen anions. While this is intuitively understood for reducible oxides, the reducibility of irreducible oxides may be modified via nanoengineering or upon inclusion of foreign species. Our calculations predict that the ability of irreducible monoclinic zirconia to release oxygen improves substantially upon deposition of rhodium. Through a comprehensive screening of Rh/ZrO2 with different size of the rhodium species, we find that a Rh adatom and a Rh4 nanocluster have the largest impact on the reducibility of zirconia. With increasing size the effect of rhodium decays. Our findings demonstrate that the phenomenon of enhanced reducibility of irreducible oxides in the presence of metals should be considered when interpreting experimental and computational results, as reactions that involve release of oxygen from an oxide support might be possible for irreducible oxides.