Exercise is essential in regulating energy metabolism and whole body insulin sensitivity. To explore the exercise signaling network we undertook a global analysis of exercise-induced changes in protein phosphorylation in human skeletal muscle biopsies revealing 1,004 unique exercise-regulated phosphosites on 562 proteins. These included substrates of known exercise-regulated kinases (AMPK, PKA, CaMK, MAPK, mTOR), yet the majority of phosphorylation sites have not previously been implicated in exercise signal transduction. Given the importance of AMPK in exercise metabolism we performed a targeted in vitro AMPK screen and employed a machine learning approach to predict exercise-regulated AMPK substrates. We identified eight highly predicted AMPK substrates including AKAP1, STIM1 and VAPA. Functional characterization revealed a previously undescribed role for AMPK-dependent phosphorylation of AKAP1 in mitochondrial respiration. These data expose the unexplored complexity of exercise signaling and provide new insights into the role of AMPK in mitochondrial biochemistry.