Capacitive deionization (CDI) is a promising technology for the desalination of brackish water due to its potentially high energy efficiency and its relatively low costs. One of the most challenging issues limiting current CDI cell performance is poor cycling stability. CDI can show highly reproducible salt adsorption capacities (SACs) for hundreds of cycles in oxygen-free electrolyte, but by contrast poor stability when oxygen is present due to a gradual oxidation of the carbon anode. This oxidation leads to increased concentration of oxygen-containing surface functional groups within the micropores of the carbon anode, increasing parasitic co-ion current and decreasing SAC. In this work, activated carbon (AC) was chemically modified with titania to achieve additional catalytic activity for oxygen-reduction reactions on the electrodes, preventing oxygen from participating in carbon oxidation. Using this approach, we show that the SAC can be increased and the cycling stability prolonged in electrochemically highly demanding oxygen-saturated saline media (5 mM NaCl). The electrochemical oxygen reduction reaction (ORR) occurring in our CDI cell was evaluated by the number of electron transfers during charging and discharging. It was found that, depending on the amount of titania, different ORR pathways take place. A loading of 15 mass% titania presents the best CDI performance and also demonstrates a favorable three-electron transfer ORR.