The maintenance of muscle function is extremely important for whole body health and exercise is essential to this process. The ubiquitin-proteasome system (UPS) is required for muscle adaptation following exercise but little is known about acute posttranslational regulation and proteome remodeling during and after high-intensity exercise. Here, we used quantitative proteomics to study ubiquitin signaling dynamics in human skeletal muscle biopsies from healthy males before, during, and after a single bout of high-intensity exercise. Exercise resulted in a marked depletion of protein ubiquitylation in the vastus lateralis muscle consistent with proteasome activation. This was also associated with acute posttranslational modification of protein abundance. Integration of these data with phosphoproteomics identified co-regulated proximal modifications suggesting a cross talk between phosphorylation and ubiquitylation. We also identified additional protein modification cross talk and showed acute activation of protein NEDDylation. In vitro experiments revealed that cAMP-dependent activation of the proteasome requires NEDD8, an ubiquitin-like protein involved in protein NEDDylation, to maintain cellular protein ubiquitylation levels. Our data reveal the complexity of ubiquitin signaling and proteome remodeling in muscle during and after high-intensity exercise. We propose a model whereby exercise and the resulting cAMP signaling activate both the proteasome and ubiquitylation via NEDDylation to rapidly remove potentially damaged proteins.