We present theoretical evidence for local magnetic moments on Ti3+ ions in oxygen-deficient anatase and rutile TiO2 observed in a recent experiment [S. Zhou, et al., Phys. Rev. B 79, 113201 (2009)]. Results of our first-principles GGA+U calculations reveal that an oxygen vacancy converts two Ti4+ ions to two Ti3+ ions in anatase phase, which results in a local magnetic moment of 1.0 $mu_B$ per Ti3+. The two Ti3+ ions, however, form a stable antiferromagnetic state, and similar antiferromagnetism is also observed in oxygen-deficient rutile phase TiO2. The calculated results are in good agreement with the experimentally observed antiferromagnetic-like behavior in oxygen-deficient Ti-O systems.