The removal of nitrous oxide (N2O) from industrial flue gases remains a significant environmental challenge due to the intrinsic kinetic stability of the N2O molecule. Among available abatement technologies, the direct catalytic decomposition of N2O into harmless N2 and O2 (deN2O) represents a promising, reagent-free solution. In this study, we systematically screened a series of catalysts obtained from Co3O4 by addition of transition elements, magnesium and aluminum (10 wt%), and analog series with addition of rhodium (Rh; 1 wt%), from which Co-Al-Rh emerged as the most active catalyst formulation. Characterization by H2-TPR and XPS indicated improvement in the redox performance and increasing weakening of the Co-O bond upon addition of a second element and of Rh. The addition of Rh resulted also in a significant enhancement in catalytic activity. Complementary kinetic studies revealed a shift in the rate-determining step (RDS) between N-O bond cleavage and O2 desorption, depending on catalyst composition. These results highlight the critical role of Co-O bond weakening in facilitating oxygen mobility and promoting activity.