Al clusters supported on TiO2(110) have been investigated using scanning tunneling microscopy. Al interacts strongly with the TiO2(110) surface at room temperature and becomes oxidized by abstracting oxygen from the interface region of the substrate. Highly oxidized Al clusters were found to disorder the TiO2 substrate in the low coverage regime (0.05 ML) illustrating that Al exhibits a strong chemical interaction with the oxide substrate. Distinct changes in the TiO2(110) substrate from a "row" structure to a "net" structure due to Al interacting with oxygen in the topmost layer of the substrate are also observed.