Titanium dioxide is an important and widely studied photocatalytic material, but to achieve photocatalytic activity under visible-light absorption, it needs to have a narrower band gap and reduced charge carrier recombination. First-principles simulations are presented in this paper to show that heterostructures of rutile TiO2 modified with nanoclusters of MgO and Ga2O3 will be new photocatalytically active materials in the UV (MgO-TiO2) and visible (Ga2O3 TiO2) regions of the solar spectrum. In particular, our investigations of a model of the excited state of the heterostructures demonstrate that upon light excitation electrons and holes can be separated onto the TiO2 surface and the metal oxide nanocluster, which will reduce charge recombination and improve photocatalytic activity. For MgO-modified TiO2, no significant band gap change is predicted, but for Ga2O3-modified TiO2, we predict a band gap change of up to 0.6 eV, which is sufficient to induce visible light absorption. Comparisons with unmodified TiO2 and other TiO2-based photocatalyst structures are presented.