Layered sodium transition metal oxides with the P2 structure, e.g. Na2/3[Ni1/3Mn2/3]O2, are regarded as candidates for Na-ion battery cathodes. On charging, extraction of Na destabilizes the P2 phase (ABBA oxide ion stacking) in which Na+ is in trigonal prismatic coordination, resulting in layer gliding and formation of an O2 phase (ABAC stacking) with octahedral coordination. However, many related compounds do not exhibit such a simple P2 to O2 transition but rather form a so called “Z”-phase. Substituting Ni by Fe in Na2/3[Ni1/3Mn2/3]O2 is attractive as it reduces cost. The Fe containing compounds, such as Na2/3[Ni1/6Mn1/2Fe1/3]O2, form a “Z”-phase when charged above 4.1 V vs. Na+/Na. By combining ex situ and operando X-ray diffraction with scanning transmission electron microscopy and simulated diffraction patterns, we demonstrate that the “Z”-phase is most accurately described as a continuously changing intergrowth structure which evolves from P2 to O2 through the OP4 structure as an intermediate. On charging, Na+ removal results in O-type stacking faults within the P2 structure which increase in proportion. At 50% O-type stacking faults, the ordered OP4 phase forms and on further charging more O-type stacking faults are formed progressing towards a pure O2 structure. This gives the superficial appearance of a solid solution. Furthermore, in contrast to some previous studies, we did not detect Fe migration at any state-of-charge using 57Fe-Mössbauer spectroscopy. It was, however, found that the Fe-substitution serves to disrupt cation ordering in the material.