Proteins are central to all of the processes of life. For their activity, they almost invariably need to interact with other macromolecules, be they nucleic acids, membranes, glycans, or other proteins. The interaction between proteins is indeed the most common mode of macromolecular interaction underpinning living systems. To understand these systems at a molecular level, it is therefore essential to identify and characterize their constituent protein-protein interactions. Despite an unprecedented growth in our knowledge of complete proteomes across all domains of life, both at the sequence level and increasingly at the structure level, the inherently low accuracy and molecular resolution of many techniques have made the characterization of protein-protein interactions one of the grand challenges of molecular biology. In this review, we survey both computational and experimental techniques for the medium- to high-throughput characterization of protein-protein interactions and discuss the potential of integrative approaches, given recent advances in sequence analysis and structure prediction.