We have investigated the photo-stability of pristine and super-hydrogenated pyrene cations C$_{16}$H$_{10+m}^+, m = 0,6, \mathrm{\ or\ } 16$) by means of gas-phase action spectroscopy. Optical absorption spectra and photo-induced dissociation mass spectra are presented. By measuring the yield of mass-selected photo-fragment ions as a function of laser pulse intensity, the number of photons (and hence the energy) needed for fragmentation of the carbon backbone was determined. Backbone fragmentation of pristine pyrene ions (C$_{16}$H$_{10}^+$) requires absorption of three photons of energy just below 3 eV, whereas super-hydrogenated hexahydropyrene (C$_{16}$H$_{16}^+$) must absorb two such photons and fully hydrogenated hexadecahydropyrene (C$_{16}$H$_{26}^+$) only a single photon. These results are consistent with previously reported dissociation energies for these ions. Our experiments clearly demonstrate that the increased heat capacity from the additional hydrogen atoms does not compensate for the weakening of the carbon backbone when pyrene is hydrogenated. In photodissociation regions, super-hydrogenated Polycyclic Aromatic Hydrocarbons (PAHs) have been proposed to serve as catalysts for H$_2$-formation. Our results indicate that carbon backbone fragmentation may be a serious competitor to H$_2$-formation at least for small hydrogenated PAHs like pyrene.