Molecular hydrogen is the most abundant molecule in the universe. A large fraction of H2 forms by association of hydrogen atoms adsorbed on polycyclic aromatic hydrocarbons (PAHs), where formation rates depend crucially on the H sticking probability. We have experimentally studied PAH hydrogenation by exposing coronene cations, confined in a radio-frequency ion trap, to gas phase atomic hydrogen. A systematic increase of the number of H atoms adsorbed on the coronene with the time of exposure is observed. Odd coronene hydrogenation states dominate the mass spectrum up to 11 H atoms attached. This indicates the presence of a barrier preventing H attachment to these molecular systems. For the second and fourth hydrogenations, barrier heights of 72 ± 6 meV and 40 ± 10 meV, respectively, are found, which are in good agreement with theoretical predictions for the hydrogenation of neutral PAHs. Our experiments, however, prove that the barrier does not vanish for higher hydrogenation states. These results imply that PAH cations, as their neutral counterparts, exist in highly hydrogenated forms in the interstellar medium. Due to this catalytic activity, PAH cations and neutrals seem to contribute similarly to the formation of H2.