As promising high-capacity cathode materials for Na-ion batteries, O3-type Na-based metal oxides always suffer from their poor air stability originating from the spontaneous extraction of Na and oxidation of transition metals when exposed to air. Herein, a combined structure modulation is proposed to tackle concurrently the two handicaps via reducing Na layers spacing and simultaneously increasing valence state of transition metals. Guided by density functional theory calculations, we demonstrate such a modulation can be subtly realized through cosubstitution of one kind of heteroatom with comparable electronegativity and another one with substantially different Fermi level, by adjusting the structure of NaNi0.5Mn0.5O2 via Cu/Ti codoping. The as-obtained NaNi0.45Cu0.05Mn0.4Ti0.1O2 exhibits an increase of 20 times in stable air-exposure period and 9 times in capacity retention after 500 cycles, and even retains its structure and capacity after being soaked in water. Such a simple and effective structure modulation reveals a new avenue for high-performance O3-type cathodes and pushes the large-scale industrialization of Na-ion batteries a decisive step forward.