Polyelectrolyte brushes are of great importance to a wide range of fields, ranging from colloidal stabilization to responsive and tunable materials to lubrication. We synthesized high-density polystyrenesulfonate (PSS) brushes using surface initiated atom transfer radical polymerization and performed neutron reflectivity (NR) and surface force measurements using a surface forces apparatus (SFA) to investigate the effect of monovalent Na+, divalent Ca2+, Mg2+, and Ba2+, and trivalent Y3+ counterions on the structure of the PSS brushes. NR and SFA results demonstrate that in monovalent salt solution the behavior of the PSS brushes agrees with scaling theory well, exhibiting two distinct regimes: the osmotic and salted brush regimes. Introducing trivalent Y3+ cations causes an abrupt shrinkage of the PSS brush due to the uptake of Y3+ counterions. The uptake of Y3+ counterions and shrinkage of the brush are reversible upon increasing the concentration of monovalent salt. Divalent cations, Mg2+, Ca2+, and Ba2+, while all significantly affecting the structure of PSS brushes, show strong ion specific effects that are related to the specific interactions between the divalent cations and the sulfonate groups. Our results demonstrate that the presence of multivalent counterions, even at relatively low concentrations, can strongly affect the structure of polyelectrolyte brushes. The results also highlight the importance of ion specificity to the structure of polyelectrolyte brushes in solution.