We report the observation of a stepwise "melting" of the low-temperature Na-vacancy order in the layered transition-metal oxide Na0.7CoO2. High-resolution neutron powder diffraction analysis indicates the existence of two first-order structural transitions, one at T1 ≈ 290 K followed by a second at T2 ≈ 400 K. Detailed analysis strongly suggests that both transitions are linked to changes in the Na mobility. Our data are consistent with a two-step disappearance of Na-vacancy order through the successive opening of first quasi-1D (T1 > T > T2) and then 2D (T > T2) Na diffusion paths. These results shed new light on previous, seemingly incompatible, experimental interpretations regarding the relationship between Na-vacancy order and Na dynamics in this material. They also represent an important step towards the tuning of physical properties and the design of tailored functional materials through an improved control and understanding of ionic diffusion.