Cobalt oxide/cobalt-based nanoparticles featuring a core-shell structure and nitrogen-doped graphene layers on alumina are obtained by pyrolysis of Co(OAc)2/phenanthroline. The resulting core-shell material (Co3O4-Co/NGr@α-Al2O3) was successfully applied in the catalytic hydrogenation of a variety of N-heteroarenes including quinolines, acridines, benzo[h], and 1,5-naphthyridine as well as unprotected indoles. The peculiar structure of the novel heterogeneous catalyst enables activation of molecular hydrogen at comparably low temperature. Both high activity and selectivity were achieved in these hydrogenation processes, to give important building blocks for bioactive compounds as well as the pharmaceutical industry.