Future NASA planetary exploration missions require batteries that can operate in deep-space environments, including high radiation and extreme temperatures, and deliver high specific energy and power density. A novel electrode material that exploits the high gravimetric and volumetric capacity of the carbon monofluoride nanoparticles with high rate capability coated by an electronically conductive thin-layer of carbon is proposed in this work as a composite cathode for lithium primary batteries. Nanoscale carbon-carbon monofluoride composites will be prepared by high energy ball-milling method. The surface coating and dispersion effect of the carbon black as conductive additive will play a beneficial role in obtaining samples with small and uniform particle size, as well as in enhancing their overall electronic conductivity. The composite anode is expected to yield high specific capacity exceeding 1000 mAh/g, high rate capability, and good shelf life. The lithium primary battery based on this new kind of CFx-based cathode material will lead a high rate primary battery with an energy density exceeding 750 Wh/kg.