The H-2 dissociation and subsequent atomic H diffusion on the oxide Mg(0001) surface have been investigated using density functional theory calculations. Our calculation indicates that at low oxygen coverages the H-2 dissociation is the rate-limiting step for surface hydrogenation. The increase of oxygen coverages from 0 to 1/4 monolayer results in decreased H-2 dissociation energy barriers from 0.93 to 0.76 eV, indicating that partial oxidized Mg(0001) surface facilitates hydrogenation. This can attributed to the enhancement of H binding strength on the oxidized Mg surface. However, the atomic H diffusion energy barriers increase with increasing H binding strength on the surface. At high oxygen coverage (1 monolayer) the diffusion of H atom from surface to subsurface is the rate-limiting step for the hydrogenation. The H atom diffusion pathways are blocked by surrounding O2- anions, hence H atom needs to overcome a significantly high energy barrier of 2.38 eV to diffuse from 1 monolayer oxide surface to subsurface. This indicates that high oxygen coverages would impede the surface hydrogenation.