We grew TiO2-Al2O3 nanocomposite coatings on titanium substrates by electrophoretic enhanced microarc oxidation (EEMAO) technique under several voltages and established a correlation between microstructure, surface hardness, and corrosion resistance of the coatings in sulfuric acid and sodium chloride solutions. Structural analysis revealed that the coatings contained anatase, rutile, alumina, and tialite phases. Formation kinetics of tialite phase was studied. It was found that increasing the voltage gives rise to a coarser morphology, i.e., larger pore size, and incorporation of more alumina nanoparticles into the layers. It is shown that surface hardness of the titanium substrates increased by a factor of 4 following EEMAO treatment. Corrosion resistance of titanium was enhanced significantly. Resistance against pitting corrosion was improved as well. We proposed a formation mechanism for the TiO2-Al2O3 composite coatings at different voltages based on the chemical and electrochemical foundations.