Current research trends on energy storage have given new impetus to the development of sodium-ion batteries. In this context, titanium phosphates with a NASICON-related structure are known to provide a stable crystal structure for sodium mobility. With adequate redox centers, these materials are studied here as attractive cathodes vs. sodium. Powdered solids of general stoichiometry Na1+x Ti2−x Fe x (PO4)3 (0 ≤ x ≤ 0.8) were obtained and electrochemically tested. The structural modifications induced by the substitution of Ti4+ by Fe3+ were analyzed by X-ray diffraction revealing an anisotropic change of the unit cell parameters. A continuous voltage decrease is observed between 2.6 and 2.0 V in the iron containing samples, which was ascribed to the contribution of the Fe3+/Fe2+ redox couple, as determined by 57Fe Mössbauer spectroscopy. A detailed analysis of this region revealed the occurrence of local orderings of inserted sodium ions. The introduction of low contents of iron (x = 0.2) involved a capacity value of 130.2 mA h g−1 after the first discharge and a good capacity retention after an extended cycling. It was correlated to the low internal resistance values for this composition.