Recent evidence shows that oppositely charged intrinsically disordered proteins (IDPs) can form high-affinity complexes that involve neither the formation of secondary or tertiary structure nor site-specific interactions between individual residues. Similar electrostatically dominated interactions have also been identified for positively charged IDPs binding to nucleic acids. These highly disordered polyelectrolyte complexes constitute an extreme case within the spectrum of biomolecular interactions involving disorder. Such interactions are likely to be widespread, since sequence analysis predicts proteins with highly charged disordered regions to be surprisingly numerous. Here, we summarize the insights that have emerged from the highly disordered polyelectrolyte complexes identified so far, and we highlight recent developments and future challenges in (i) establishing models for the underlying highly dynamic structural ensembles, (ii) understanding the novel binding mechanisms associated with them, and (iii) identifying the functional consequences.