The ability of microorganisms to sense and respond to sudden changes in their environment is often based on regulatory systems comprising reversible protein phosphorylation. The archaellum (former: archaeal flagellum) is used for motility in Archaea and therefore functionally analogous to the bacterial flagellum. In contrast with archaellum-mediated movement in certain members of the Euryarchaeota, this process, including its regulation, remains poorly studied in crenarchaeal organisms like Sulfolobus species. Recently, it was shown in Sulfolobus acidocaldarius that tryptone limiting conditions led to the induction of archaella expression and assembly. Here we have identified two proteins, the FHA domain-containing protein ArnA and the vWA domain-containing protein ArnB that are involved in regulating archaella expression in S.acidocaldarius. Both proteins are phosphorylated by protein kinases in vitro and interact strongly in vivo. Phenotypic analyses revealed that these two proteins are repressors of archaella expression. These results represent the first step in understanding the networks that underlie regulation of cellular motility in Crenarchaeota and emphasize the importance of protein phosphorylation in the regulation of cellular processes in the Archaea.