This invention relates to novel catalyst compositions based on ruthenium or osmium carbene-complex catalysts, pref. of the Grubbs-I, -II or -III type or fluorenylidene analogues thereof, and terminal olefins, pref. enol ethers such as ethyl vinyl ether (EVE or VEE) as co-catalysts and to a process for selectively hydrogenating nitrile rubbers in the presence of such catalyst compositions, pref. with a preceding metathesis step using the same complex catalyst as in the hydrogenation step.