The low coverage adsorption of gallium on a hydrogen-contaminated Al-terminated α-Al2O3(0001) surface is studied theoretically using first-principles density functional calculations with periodic boundary conditions. Initial computations to form the hydrogen-contaminated surface identified two stable hydrogen adsorption sites, one where the hydrogen is chemisorbed and one where it is physisorbed. Although interaction between the gallium atom and the chemisorbed hydrogen leads to a weakening of the hydrogen to Al2O3 surface adhesion, this weakening is insufficient to result in a loss of hydrogen from the Al 2O3 surface. For the physisorbed hydrogen, addition of gallium can lead to a strongly bound gallium/hydrogen pair that shows much less adhesion to the Al2O3 surface. This provides direct theoretical support for a gallium cleaning effect.