Ab initio density functional theory (DFT) calculations are performed to study the adsorption of H2 molecules on a Ti-doped Mg(0001) surface. We find that two hydrogen molecules are able to dissociate on top of the Ti atom with very small activation barriers (0.103 and 0.145 eV for the first and second H2 molecules, respectively). Additionally, a molecular adsorption state of H2 above the Ti atom is observed for the first time and is attributed to the polarization of the H2 molecule by the Ti cation. Our results parallel recent findings for H2 adsorption on Ti-doped carbon nanotubes or fullerenes. They provide new insight into the preliminary stages of hydrogen adsorption onto Ti-incorporated Mg surfaces.