Using mass spectrometry-based phosphoproteomics, we quantified 23,126 phosphosites in the skeletal muscle of five genetically distinct inbred mouse strains exposed to two controlled dietary environments, with and without acute insulin treatment. Almost half of the insulin-regulated phosphoproteome was altered by genetic background independently of diet, and high-fat high-sugar feeding also affected insulin signalling in a strain-dependent manner. Our data illuminated signalling network organisation principles, including the uncoupling of phosphosites targeted by the same kinase. Associating diverse signalling responses with insulin-stimulated glucose uptake uncovered regulators of muscle insulin responsiveness, including the regulatory phosphosite S469 on Pfkfb2, a key glycolytic enzyme.