Traditional lithium-ion batteries that are based on layered Li intercalation electrode materials are limited by the intrinsically low theoretical capacities of both electrodes and cannot meet the increasing demand for energy. A facile route for the synthesis of a new type of composite nanofibers, namely carbon nanofibers decorated with molybdenum disulfide sheets (CNFs@MoS2), is now reported. A synergistic effect was observed for the two-component anode, triggering new electrochemical processes for lithium storage, with a persistent oxidation from Mo (or MoS2) to MoS3 in the repeated charge processes, leading to an ascending capacity upon cycling. The composite exhibits unprecedented electrochemical behavior with high specific capacity, good cycling stability, and superior high-rate capability, suggesting its potential application in high-energy lithium-ion batteries.