In this review, we summarize computational and experimental data gathered so far showing that structural disorder is abundant within paramyxoviral nucleoproteins (N) and phosphoproteins (P). In particular, we focus on measles, Nipah, and Hendra viruses and highlight both commonalities and differences with respect to the closely related Sendai virus. The molecular mechanisms that control the disorder-to-order transition undergone by the intrinsically disordered C-terminal domain (NTAIL) of their N proteins upon binding to the C-terminal X domain (XD) of the homologous P proteins are described in detail. By having a significant residual disorder, NTAIL–XD complexes are illustrative examples of “fuzziness”, whose possible functional significance is discussed. Finally, the relevance of N–P interactions as promising targets for innovative antiviral approaches is underscored, and the functional advantages of structural disorder for paramyxoviruses are pinpointed.