End-tethered polyelectrolyte layers (“brushes”) shrink monotonically in response to addition of mono-valent salt, which also produces corresponding monotonic changes in the range of the repulsive normal forces exerted by such brushes. High swelling and very low frictional forces have been reported under low salt concentrations. A new pattern of behavior is demonstrated here via surface force measurement on polyelectrolyte brushes in the presence of multi-valent ionic interactions, introduced via tri-valent aluminum cations (Al3+) or aggregates of cationic surfactants. Very low concentrations of added Al3+ or surfactant produce much stronger shrinkage of the brush than does mono-valent salt. Normal forces become strongly attractive under these circumstances. Multi-valent interactions enable tuning of polyelectrolyte brush structure and properties over a wide range, from compact, stiff and sticky to swollen, soft and repulsive.