Following the sequencing of the human genome and many other organisms, research on protein-coding genes and their functions (functional genomics) has intensified. Subsequently, with the observation that proteins are indeed the molecular effectors of most cellular processes, the discipline of proteomics was born. Clearly, proteins do not function as single entities but rather as a dynamic network of team players that have to communicate. Though genetic (yeast two-hybrid Y2H) and biochemical methods (co-immunoprecipitation Co-IP, affinity purification AP) were the methods of choice at the beginning of the study of protein-protein interactions (PPI), in more recent years there has been a shift towards proteomics-based methods and bioinformatics-based approaches. In this review, we first describe in depth PPIs and we make a strong case as to why unraveling the interactome is the next challenge in the field of proteomics. Furthermore, classical methods of investigation of PPIs and structure-based bioinformatics approaches are presented. The greatest emphasis is placed on proteomic methods, especially native techniques that were recently developed and that have been shown to be reliable. Finally, we point out the limitations of these methods and the need to set up a standard for the validation of PPI experiments.