Olivine NaFePO4 has recently attracted the attention of the scientific community as a promising cathode material for Na-ion batteries. In this work we combine density functional theory (DFT) calculations and high resolution synchrotron X-ray diffraction (HRXRD) experiments to study the phase stability of NaxFePO4 along the whole range of sodium compositions (0 ≤x≤ 1). DFT calculations reveal the existence of two intermediate structures governing the phase stability at x = 2/3 and x = 5/6. This is in contrast to isostructural LiFePO4, which is a broadly used cathode in Li-ion batteries. Na2/3FePO4 and Na5/6FePO4 ground states both align vacancies diagonally within the ab plane, coupled to a Fe(2+)/Fe(3+) alignment. HRXRD data for NaxFePO4 (2/3 < x < 1) materials show common superstructure reflections up to x = 5/6 within the studied compositions. The computed intercalation voltage profile shows a voltage difference of 0.16 V between NaFePO4 and Na2/3FePO4 in agreement with the voltage discontinuity observed experimentally during electrochemical insertion.