Molecular communication in biology is mediated by protein interactions. According to the current paradigm, the specificity and affinity required for these interactions are encoded in the precise complementarity of binding interfaces. Even proteins that are disordered under physiological conditions or that contain large unstructured regions commonly interact with well-structured binding sites on other biomolecules. Here we demonstrate the existence of an unexpected interaction mechanism: the two intrinsically disordered human proteins histone H1 and its nuclear chaperone prothymosin-α associate in a complex with picomolar affinity, but fully retain their structural disorder, long-range flexibility and highly dynamic character. On the basis of closely integrated experiments and molecular simulations, we show that the interaction can be explained by the large opposite net charge of the two proteins, without requiring defined binding sites or interactions between specific individual residues. Proteome-wide sequence analysis suggests that this interaction mechanism may be abundant in eukaryotes. A high-affinity complex of histone H1 and prothymosin-α reveals an unexpected interaction mechanism, where the large opposite net charge enables the two proteins to remain highly disordered even in the complex. Disordered protein regions have been increasingly implicated in high-affinity protein–protein interactions. However, once the resulting protein complexes have formed, at least one interacting protein partner has been found to be stably folded. Using a suite of independent biophysical approaches, Ben Schuler and colleagues reveal a ultrahigh-affinity (picomolar) complex between two proteins (histone H1 and its nuclear chaperone prothymosin-α) that both remain fully disordered when bound to each other. High-affinity binding results from numerous, dynamic and non-specific electrostatic interactions along the extended chains of the highly charged polypeptides. This structural feature is prevalent among signalling molecules in eukaryotes, including in humans.