Sodium-ion batteries (SIBs) are potential cost-effective solutions for stationary energy storage applications. Unavailability of suitable anode materials, however, is one of the important barriers to the maturity of SIBs. Here, we report a Na2+xTi4O9/C composite as a promising anode candidate for SIBs with high capacity and cycling stability. This anode is characterized by a capacity of 124 mAh g-1 (plus 11 mAh g-1 contributed by carbon black), an average discharge potential of 0.9 V vs Na/Na+, a good rate capability and a high stability (89% capacity retention after 250 cycles at a rate of 1 C). The mechanisms of sodium insertion/deinsertion and of the formation of Na2+xTi4O9/C are investigated with the aid of various ex/in situ characterization techniques. The in situ formed carbon is necessary for the formation of the reduced sodium titanate. This synthesis method may enable the convenient synthesis of other composites of crystalline phases with amorphous carbon.