We use first-principles density functional theory calculations to analyze the effect of chromia nanocluster modification on TiO2 rutile (110) and anatase (101) surfaces, in which both dry/perfect and wet/hydroxylated TiO2 surfaces are considered. We show that the adsorption of chromia nanoclusters on both surfaces is favorable and results in a reduction of the energy gap due to a valence band upshift. A simple model of the photoexcited state confirms this red shift and shows that photoexcited electrons and holes will localize on the chromia nanocluster. The oxidation states of the cations show that Ti3+, Cr4+, and Cr2+ (with no Cr6+) can be present. To probe potential reactivity, the energy of oxygen vacancy formation is shown to be significantly reduced compared to that of pure TiO2 and chromia. Finally, we show that inclusion of water on the TiO2 surface, to begin inclusion of environment effects, has no notable effect on the energy gap or oxygen vacancy formation. These results help us to understand earlier experimental work on chromia-modified anatase TiO2 and demonstrate that chromia-modified TiO2 presents an interesting composite system for photocatalysis.