In the eukaryotic 26S proteasome, the 20S particle is regulated by six AAA ATPase subunits and, in archaea, by a homologous ring complex, PAN. To clarify the role of ATP in proteolysis, we studied how nucleotides bind to PAN. Although PAN has six identical subunits, it binds ATPs in pairs, and its subunits exhibit three conformational states with high, low, or no affinity for ATP. When PAN binds two ATPγS molecules or two ATPγS plus two ADP molecules, it is maximally active in binding protein substrates, associating with the 20S particle, and promoting 20S gate opening. However, binding of four ATPγS molecules reduces these functions. The 26S proteasome shows similar nucleotide dependence. These findings imply an ordered cyclical mechanism in which two ATPase subunits bind ATP simultaneously and dock into the 20S. These results can explain how these hexameric ATPases interact with and "wobble" on top of the heptameric 20S proteasome.