The AAA+ ATPases are enzymes containing a P-loop NTPase domain, and function as molecular chaperones, ATPase subunits of proteases, helicases or nucleic-acid-stimulated ATPases. All available sequences and structures of AAA+ protein domains were compared with the aim of identifying the definitive sequence and structure features of these domains and inferring the principal events in their evolution. An evolutionary classification of the AAA+ class was developed using standard phylogenetic methods, analysis of shared sequence and structural signatures, and similarity-based clustering. This analysis resulted in the identification of 26 major families within the AAA+ ATPase class. We also describe the position of the AAA+ ATPases with respect to the RecA/F1, helicase superfamilies I/II, PilT, and ABC classes of P-loop NTPases. The AAA+ class appears to have undergone an early radiation into the clamp-loader, DnaA/Orc/Cdc6, classic AAA, and "pre-sensor 1 beta-hairpin" (PS1BH) clades. Within the PS1BH clade, chelatases, MoxR, YifB, McrB, Dynein-midasin, NtrC, and MCMs form a monophyletic assembly defined by a distinct insert in helix-2 of the conserved ATPase core, and additional helical segment between the core ATPase domain and the C-terminal alpha-helical bundle. At least 6 distinct AAA+ proteins, which represent the different major clades, are traceable to the last universal common ancestor (LUCA) of extant cellular life. Additionally, superfamily III helicases, which belong to the PS1BH assemblage, were probably present at this stage in virus-like "selfish" replicons. The next major radiation, at the base of the two prokaryotic kingdoms, bacteria and archaea, gave rise to several distinct chaperones, ATPase subunits of proteases, DNA helicases, and transcription factors. The third major radiation, at the outset of eukaryotic evolution, contributed to the origin of several eukaryote-specific adaptations related to nuclear and cytoskeletal functions. The new relationships and previously undetected domains reported here might provide new leads for investigating the biology of AAA+ ATPases.