Organisms have evolved motility organelles that allow them to move to favorable habitats. Cells integrate environmental stimuli into intracellular signals to motility machineries to direct this migration. Many motility organelles are complex surface appendages that have evolved a tight, hierarchical regulation of expression. In the crenearchaeon Sulfolobus acidocaldarius, biosynthesis of the archaellum is regulated by regulatory network proteins that control expression of archaellum components in a phosphorylation-dependent manner. A major trigger for archaellum expression is nutrient starvation, but although some components are known, the regulatory cascade triggered by starvation is poorly understood. In this work, we identify the starvation-induced Ser/Thr protein kinase ArnS (Saci_1181) which is located proximally to the archaellum operon. Deletion of arnS results in reduced motility, though the archaellum is properly assembled. Therefore, our experimental and modelling results indicate that ArnS plays an essential role in the precisely controlled expression of archaellum components during starvation-induced motility in Sulfolobus acidocaldarius. Furthermore we combine in vivo experiments and mathematical models to describe for the first time in archaea the dynamics of key regulators of archaellum expression.