Pure and carbon (C)-coated CaMoO4 were synthesized by solution precipitation and solgel methods, and their electrochemical properties were studied vs Li by galvanostatic cycling and cyclic voltammetry (CV). Combined X-ray diffraction, SEM, and TEM results revealed the formation of nanocrystalline particles with the scheelite structure, the morphology being a function of the synthetic procedure. TEM of 10% C-coated CaMoO4 shows the amorphous nature of carbon on the crystalline particles with a thickness of 8-12 nm. Galvanostatic data in the voltage range of 0.005-2.5 V up to 50 cycles at a rate of 60 mA/g revealed that the 10% C-coated CaMoO4 gave the highest reversible capacities. At the 20th discharge cycle, the capacity values (mA h/g) are as follows: solution precipitated, 190; sol-gel, 268; 5% C-coated, 401; and 10% C-coated, 508. The latter value corresponds to 3.8 mol of recyclable Li. The improvement in the interparticle electronic conductivity imparted by the C-coating led to superior performance. The Coulombic efficiency for all the compositions is >98%. Galvanostatic cycling results are supplemented by the CV data. A plausible mechanism for charge-discharge cycling has been proposed.