We prove the direct link between low temperature magnetism and high temperature sodium ordering in NaxCoO2 using the example of a heretofore unreported magnetic transition at 8 K which involves a weak ferromagnetic moment. The 8 K feature is characterized in detail and its dependence on a diffusive sodium rearrangement around 200 K is demonstrated. Applying muons as local probes this process is shown to result in a reversible phase separation into distinct magnetic phases that can be controlled by specific cooling protocols. Thus the impact of ordered sodium Coulomb potential on the CoO2 physics is evidenced opening new ways to experimentally revisit the NaxCoO2 phase diagram.