In gram-positive bacteria, phosphorylated arginine functions as a protein degradation signal in a similar manner as ubiquitin in eukaryotes. The protein-arginine phosphorylation is mediated by the McsAB complex, where McsB possesses kinase activity and McsA modulates McsB activity. Although mcsA and mcsB are regulated within the same operon, the role of McsA in kinase activity has not yet been clarified. In this study, we determined the molecular mechanism by which McsA regulates kinase activity. The crystal structure of the McsAB complex shows that McsA binds to the McsB kinase domain through a second zinc-coordination domain and the subsequent loop region. This binding activates McsB kinase activity by rearranging the catalytic site, preventing McsB self-assembly, and enhancing stoichiometric substrate binding. The first zinc-coordination and coiled-coil domains of McsA further activate McsB by reassembling the McsAB oligomer. These results demonstrate that McsA is the regulatory subunit for the reconstitution of the protein-arginine kinase holoenzyme. This study provides structural insight into how protein-arginine kinase directs the cellular protein degradation system.