Protein-protein interactions (PPIs) are a major organizing principle of cellular processes. To date, large-scale efforts to investigate the role of PPIs have focused on generating static maps of PPI networks (PPINs). However, the extent to which PPINs are adaptively rewired under different contexts, and the consequences of that rewiring, are poorly understood. Here, we have used quantitative mass spectrometry (qMS) to investigate how a common oncogenic mutation affects PPI wiring in the Epidermal Growth Factor Receptor (EGFR) network, arguably one of the most important signaling networks in cancer. Analyzing >1700 affinity purifications by qMS and mapping >4000 PPIs, we show that the EGFR network is extensively rewired as the dosage of mutant KRAS (mtKRAS) increases, demonstrating that mtKRAS adaptively reconfigures cells at a PPI level. This physical rewiring drives substantial changes in signal flow, transcriptional regulation and biological behavior. Alterations in the most rewired proteins are prognostic of colorectal cancer (CRC) patient outcomes. These findings provide new insights into the dynamic reorganization of PPI networks in disease and provide new opportunities for network medicine based approaches in cancer.