Layered oxides, such as NaxMeO2 (Me = transition metal, x = 0–1), are believed to be the most promising positive electrode materials for Na-ion batteries because of their high true density, large capacities, high working potentials, and reversibility. This study identified Na5/6[Ni1/3Mn1/6Fe1/6Ti1/3]O2 as an optimal composition for use as an O3-type positive electrode material in Na-ion batteries on the basis of a comprehensive phase diagram, where the end members of the triangular phase diagram were Na2/3[Ni1/32+Mn2/34+]O2, Na2/3[Ni1/32+Ti2/34+]O2, and the hypothetical composition Na4/3[Ni1/32+Fe2/33+]O2. By investigating the effects of the partial substitution of Mn4+ with Fe3+ and Ti4+ within the Na(2/3+x)[Ni1/3Mn(2/3–x–y)FexTiy]O2 system, we optimized the capacity, working potential, and cycle performance. Substitution with Fe enhanced the discharge capacity due to the increased Na+ content in the initial composition, although it also led to a reduced cycling stability derived from irreversible Fe migration to the Na layers. In contrast, substitution with Ti improved the working potential and cycling stability, although an excessive Ti content caused capacity degradation with cycling. We found that the O3-type Na5/6[Ni1/3Mn1/6Fe1/6Ti1/3]O2 demonstrated an excellent cycle stability with minimal capacity loss over 250 cycles, which was attributed to the suppression of irreversible transition metal migration.