We investigated the effect of counterion valence on the structure and swelling behavior of polyelectrolyte brushes using a nonlocal density functional theory that accounts for the excluded-volume effects of all ionic species and intrachain and electrostatic correlations. It was shown that charge correlation in the presence of multivalent counterions results in collapse of a polyelectrolyte brush at an intermediate polyion grafting density. At high grafting density, the brush reswells in a way similar to that in a monovalent ionic solution. In the presence of multivalent counterions, the nonmonotonic swelling of a polyelectrolyte brush in response to the increase of the grafting density can be attributed to a competition of the counterion-mediated electrostatic attraction between polyions with the excluded-volume effect of all ionic species. While a polyelectrolyte brush exhibits an "osmotic brush" regime at low salt concentration and a "salted brush" regime at high salt concentration regardless of the counterion valence, we found a smoother transition as the valence of the counterions increases. As observed in recent experiments, a quasi-power-law dependence of the brush thickness on the concentration ratio can be identified when the monovalent counterions are replaced with trivalent counterions at a fixed ionic strength.