The interactions of proteins and polyelectrolytes lead to diverse applications in separations, delivery and wound repair, and are thus of interest to scientists in e.g. (a) glycobiology, (b) tissue engineering, (c) biosensing, and (d) pharmacology. This breadth is accompanied by an assortment of contexts and models in which polyelectrolytes are seen as (a) protein cognates assisting in complex cellular roles, (b) surrogates for the extracellular matrix, mimicking its hydration, mechanical and sequestering properties, (c) benign hosts that gently entrap, deposit and tether protein substrate specificity, and (d) selective but non-specific agents that modify protein solubility. Unsurprisingly, this literature is somewhat segregated by objectives and paradigms. We hope this review, which emphasizes publications over the last 8 years, represents and also counterbalances that divergence. An ongoing theme is the role of electrostatics, and we show how this leads to the variety of physical forms taken by protein-polyelectrolyte complexes. We present approaches towards analysis and characterization, motivated by the goal of structure-property elucidation. Such understanding should guide in applications, our third topic. We present recent developments in modeling and simulations of protein-polyelectrolyte systems. We close with a prospective on future developments in this field.