Polyelectrolytes can show strong adsorption at water-water interfaces formed by phase separation of two polymers in aqueous solution. We demonstrate this for a model system consisting of neutral polymer A and weakly positively charged polymer B. When polyelectrolyte is added with similar chemical composition as polymer A, but charge of opposite sign as polymer B, interfacial accumulation is observed. We hypothesize this accumulation to be complexation at the water-water interface. This adsorption surprisingly persists even at high salt concentrations and has only a limited effect on the interfacial tension. Complexation of polyelectrolytes at water-water interfaces may provide a new path towards the stabilization of water-in-water emulsions.