Cobalt phosphide (CoP) nanoparticles which were uniformly embedded in N-doped C nanosheets (CNSs) were fabricated via the simple one-step calcination of a Co-based metal–organic framework (MOF) and red P and exhibited a high capacity, fast kinetics, and a long cycle life. This CoP/CNS composite contained small CoP particles (approximately 11.3 nm) and P–C bonds. When its electrochemical properties were evaluated by testing CoP/Na coin cells, the composite delivered a Na-storage capacity of 598 mAh·g^-1 at 0.1 A·g^-1 according to the total mass of the composite, which means that the capacity of pure CoP reached 831 mAh·g^-1. The composite also exhibited a high rate capability and long-term cyclability (174 mAh·g^-1 at 20 A·g^-1 and 98.5% capacity retention after 900 cycles at 1 A·g^-1), which are commonly attributed to robust P–C bonding and highly conductive CNSs. When the reaction mechanism of the CoP/CNS composite was investigated, a conversion reaction expressed as CoP + 3Na⁺ + 3e^- ↔ Co + Na₃P was observed. The outstanding Na-storage properties of the CoP/CNS composite may suggest a new strategy for developing high-performance anode materials for Na-ion batteries.