Cellular processes arise from the dynamic organization of proteins in networks of physical interactions. Mapping the complete network of biologically relevant protein-protein interactions, the interactome, has therefore been a central objective of high-throughput biology. Yet, because widely used methods for high-throughput interaction discovery rely on heterologous expression or genetically manipulated cell lines, the dynamics of protein interactions across physiological contexts are poorly understood. Here, we use a quantitative proteomic approach combining protein correlation profiling with stable isotope labelling of mammals (PCP-SILAM) to map the interactomes of seven mouse tissues. The resulting maps provide the first proteome-scale survey of interactome dynamics across mammalian tissues, revealing over 27,000 unique interactions with an accuracy comparable to the highest-quality human screens. We identify systematic suppression of cross-talk between the evolutionarily ancient housekeeping interactome and younger, tissue-specific modules. Rewiring of protein interactions across tissues is widespread, and is poorly predicted by gene expression or coexpression. Rewired proteins are tightly regulated by multiple cellular mechanisms and implicated in disease. Our study opens up new avenues to uncover regulatory mechanisms that shape in vivo interactome responses to physiological and pathophysiological stimuli in mammalian systems.