In eukaryotes, the 20 S proteasome is the proteolytic core of the 26 S proteasome, which degrades ubiquitinated proteins in an ATP-dependent process. Archaebacteria lack ubiquitin and 26 S proteasomes but do contain 20 S proteasomes. Many archaebacteria, such as Methanococcus jannaschii, also contain a gene (S4) that is highly homologous to the six ATPases in the 19 S (PA700) component of the eukaryotic 26 S proteasome. To test if this putative ATPase may regulate proteasome function, we expressed it in Escherichia coli and purified the 50-kDa product as a 650-kDa complex with ATPase activity. When mixed with the well characterized 20 S proteasomes from Thermoplasma acidophilum and ATP, this complex stimulated degradation of several unfolded proteins 8-25-fold. It also stimulated proteolysis by 20 S proteasomes from another archaebacterium and mammals. This effect required ATP hydrolysis since ADP and the nonhydrolyzable analog, 5'-adenylyl beta, gamma-imidophosphate, were ineffective. CTP and to a lesser extent GTP and UTP were also hydrolyzed and also stimulated proteolysis. We therefore named this complex PAN for proteasome-activating nucleotidase. However, PAN did not promote the degradation of small peptides, which, unlike proteins, should readily diffuse into the proteasome. This ATPase complex appears to have been the evolutionary precursor of the eukaryotic 19 S complex, before the coupling of proteasome function to ubiquitination.