Metalloproteases of the AAA family play a crucial role in protein quality control within the cytoplasmic membrane of bacteria and the inner membrane of eukaryotic organelles. These membrane-anchored hexameric enzymes are composed of an N-terminal domain with one or two transmembrane helices, a central AAA ATPase module and a C-terminal Zn2 +-dependent protease. While the latter two domains have been well studied, so far little is known about the N-terminal regions. Here, in an extensive bioinformatic and structural analysis, we identified three major, non-homologous groups of N-domains in AAA metalloproteases. By far the largest one is the FtsH-like group of bacteria and eukaryotic organelles. The other two groups are specific to Yme1, one found in plants, fungi, and basal metazoans, and the other exclusively in animals. Using NMR and crystallography, we determined the subunit structure and hexameric assembly of E. coli FtsH-N, exhibiting an unusual α + β fold, and the conserved part of fungal Yme1-N from Saccharomyces cerevisiae, revealing a tetratricopeptide repeat (TPR) fold. Our bioinformatic analysis showed that, uniquely among these proteins, the N-domain of Yme1 from the cnidarian Hydra vulgaris contains both the TPR region seen in basal metazoans and a region of homology to the N-domains of animals. It thus is a modern-day representative of an intermediate in the evolution of animal Yme1 from basal eukaryotic precursors.