We report on a strong non-additive effect of protons and other cations on the structural dynamics of liquid water, which is revealed using dielectric relaxation spectroscopy in the frequency range of 1-50 GHz. For pure acid solutions, protons are known to have a strong structuring effect on water, leading to a pronounced decrease of the dielectric response. We observe that this structuring is reduced when protons are co-solvated with salts. This reduction is exclusively observed for combinations of protons with other ions; for all studied solutions of co-solvated salts the effect on the structural dynamics of water is observed to be purely additive, even up to high concentrations. We derive an empirical model that quantitatively describes the non-additive effect of co-solvated protons and cations. We argue that the effect can be explained from the special character of the proton in water and that Coulomb fields exerted by other cations, in particular doubly charged cations like Mg(2+) and Ca(2+), induce a localization of the H+aq hydration structures.