A theory of superconductivity in the iron-based materials requires an understanding of the phase diagram of the normal state. In these compounds, superconductivity emerges when stripe spin density wave (SDW) order is suppressed by doping, pressure or atomic disorder. This magnetic order is often pre-empted by nematic order, whose origin is yet to be resolved. One scenario is that nematic order is driven by orbital ordering of the iron 3d-electrons that triggers stripe SDW order. Another is that magnetic interactions produce a spin-nematic phase, which then induces orbital order. In this article, we report the observation by neutron powder diffraction of an additional four- fold-symmetric phase in Ba1-xNaxFe2As2 close to the suppression of SDW order, which is consistent with the predictions of magnetically-driven models of nematic order.