We report that a partially oxygen deficient LiTi2(PO4)3 shows a much better rate capability as a cathode material for lithium-ion batteries compared to stoichiometric LiTi2(PO4)3. A combination of X-ray diffraction (XRD), X-ray photoelectron spectroscopy (XPS), electrochemistry, and first-principles calculations was used to determine and rationalize the structural and electrical changes that occur with different heat treatment atmospheres. XRD and XPS experiments confirmed that some Ti4+ transformed to Ti3+ in oxygen deficient LiTi2(PO4)3 heat treated under N2; Ti3+ was detected and the lattice parameter increased compared to that of LiTi2(PO4)3. Electrical conductivity measurements indicated an increase in the electronic conductivity of nearly two orders of magnitude for the oxygen deficient LiTi2(PO4)3 sample compared to LiTi2(PO4)3. First-principles calculations suggest that the oxygen vacancies could be formed in LiTi2(PO4)3 under oxygen-poor conditions, and this may significantly decrease the donor levels of other possible donor defects and thus improve the electronic mobility.