Protein-protein-interaction networks (PPINs) organize fundamental biological processes, but how oncogenic mutations impact these interactions and their functions at a network-level scale is poorly understood. Here, we analyze how a common oncogenic KRAS mutation (KRASG13D) affects PPIN structure and function of the Epidermal Growth Factor Receptor (EGFR) network in colorectal cancer (CRC) cells. Mapping >6000 PPIs shows that this network is extensively rewired in cells expressing transforming levels of KRASG13D (mtKRAS). The factors driving PPIN rewiring are multifactorial including changes in protein expression and phosphorylation. Mathematical modelling also suggests that the binding dynamics of low and high affinity KRAS interactors contribute to rewiring. PPIN rewiring substantially alters the composition of protein complexes, signal flow, transcriptional regulation, and cellular phenotype. These changes are validated by targeted and global experimental analysis. Importantly, genetic alterations in the most extensively rewired PPIN nodes occur frequently in CRC and are prognostic of poor patient outcomes.