One of the greatest challenges of the post-genomic era is the construction of a more comprehensive human protein interaction map. While this process may take many years to complete, the development of stringent high throughput techniques and the emergence of complementary assays mean that the aim of building a detailed binary map of the human interactome is now a very realistic goal. In particular, methods which facilitate the analysis of large numbers of membrane-protein interactions mean that it will be possible to construct more extensive networks, which in turn provide new insights into the functional connectivity between intra- and extra-cellular processes. This is important as many therapeutic strategies are designed to elicit effects via 'tractable' cell-surface proteins. Therefore, the construction of maps depicting the complexity of trans-cellular communication networks will not only improve our understanding of physiological processes, it will also aid the design of rational therapeutic strategies, with fewer potential side effects. This review aims to provide a basic insight into the approaches currently being used to construct binary human protein interaction networks, with particular reference to newer techniques, which have the potential to extend network coverage and aid the conditional annotation of interactome-scale protein interaction maps.