Capacitive deionization (CDI) provides a promising option for affordable freshwater while simultaneously storing energy, but its large-scale application is usually limited owing to the poor performance of conventional materials in natural (oxygenated) saline water. Herein, we report heterointerface optimization in a covalent organic framework (COF)-on-MXene heterostructure achieving a high CDI performance for desalination of oxygenated saline water. The 2D heterostructure with the optimal core-shell architecture inherits the high conductivity and reversible ion intercalation/deintercalation ability of MXene, and the hierarchical porous structure, large porosity, and extraordinary redox capacity of COFs. Thanks to the heterointerface optimization, the MXene@COF heterostructure exhibits a very stable cycling performance over 100 CDI cycles with a maximum NaCl adsorption capacity of 53.1 mg g-1 in oxygenated saline water, among the state-of-the-art values for CDI electrodes and also exceeding those of most MXene-based or 2D materials. This study highlights the importance of heterointerface optimization in MXene-organic 2D heterostructures to promote CDI of natural (oxygenated) saline water.