Oxygen deficient MoxOy 200 nm-thick particles were synthesized by a citrate sol-gel method using ammonium heptamolybdate tetrahydrate as a source of Mo and heat treated with a small fraction of zirconia under reducing atmosphere. The samples were investigated by X-ray powder diffraction (XRD), thermal gravimetric analysis (TGA), scanning electron microscope (SEM) and Raman spectroscopy (RS). The structural analyses show that the composite is a blend formed by layered α-MoO3, orthorhombic oxygen deficient phases MoO3−δ with δ = 0.25 (γ-Mo4O11) and α-ZrMo2O8. The insertion of lithium into the lattice was performed by electrochemical method. Redox peaks were observed for the MoO3−δ composite attributed to distinct Li+ ion insertion/extraction reactions in the MoO3 and Mo4O11 hosts. The cyclic performance revealed improved reversibility, rate capability, and electrochemical stability of the ZrMo2O8-decorated composite with respect to the bare molybdenum oxides. At C/10 rate, the composite delivered a stable reversible capacity of 135 mAh g−1 after the 50th cycle. At a rate of 2C the reversible capacity is maintained at 118 mAh g−1, approximately twice the capacity observed for the MoO3 particles alone.