We present the first experimental evidence for the existence of an exosome-like protein complex in Archaea. In Eukarya, the exosome is essential for many pathways of RNA processing and degradation. Co-immunoprecipitation with antibodies directed against the previously predicted Sulfolobus solfataricus orthologue of the exosome subunit ribosomal-RNA-processing protein 41 (Rrp41) led to the purification of a 250-kDa protein complex from S. solfataricus. Approximately half of the complex cosediments with ribosomal subunits. It comprises four previously predicted orthologues of the core exosome subunits from yeast (Rrp41, Rrp42, Rrp4 and Csl4 (cepl synthetic lethality 4; an RNA-binding protein and exosome sub-unit)), whereas other predicted subunits were not found. Surprisingly, the archaeal homologue of the bacterial DNA primase DnaG was tightly associated with the complex. This suggests an RNA-related function for the archaeal DnaG-like proteins. Comparison of experimental data from different organisms shows that the minimal core of the exosome consists of at least one phosphate-dependent ribonuclease PH homologue, and of Rrp4 and Csl4. Such a protein complex was probably present in the last common ancestor of Archaea and Eukarya.