NaFeTiO₄ nanorods of high yields (with diameters in the range of 30–50 nm and lengths of up to 1–5 μm) were synthesized by a facile sol–gel method and were utilized as an anode material for sodium-ion batteries for the first time. The obtained NaFeTiO₄ nanorods exhibit a high initial discharge capacity of 294 mA·h·g^-1 at 0.2 C (1 C = 177 mA·g^–1), and remain at 115 mA·h·g^–1 after 50 cycles. Furthermore, multi-walled carbon nanotubes (MWCNTs) were mechanically milled with the pristine material to obtain NaFeTiO₄/MWCNTs. The NaFeTiO₄/ MWCNTs electrode exhibits a significantly improved electrochemical performance with a stable discharge capacity of 150 mA·h·g^–1 at 0.2 C after 50 cycles, and remains at 125 mA·h·g^–1 at 0.5 C after 420 cycles. The NaFeTiO₄/MWCNTs//Na₃V₂(PO₄)₃/C full cell was assembled for the first time; it displays a discharge capacity of 70 mA·h·g^-1 after 50 cycles at 0.05 C, indicating its excellent performances. X-ray photoelectron spectroscopy, ex situ X-ray diffraction, and Raman measurements were performed to investigate the initial electrochemical mechanisms of the obtained NaFeTiO₄/MWCNTs.