We investigate the rheology of dense cohesive granular media outside the quasistatic regime using molecular dynamic simulations of homogeneous plane shear flow in the steady state. Friction as well as dilatancy are governed by two dimensionless numbers, the inertial number and the cohesion number. The internal friction coefficient and the solid fraction depend linearly on the inertial number, as in the cohesionless case. Weak cohesion leads to an expansion of the material, while the friction remains unchanged. Above a characteristic cohesion strength, a strong increase of friction combined with a decrease of solid fraction is observed. We relate this behavior to the growing space-time heterogeneities and to the increase of the cohesion-enhanced microscopic friction between the grains.