With the growing flood of genomic sequence data, methods for classifying and annotating sequences have achieved critical importance. Several such methods have been explored for proteins, including classification by pathway, 3D-structure, and mechanism. Here we will argue that, as for living beings, the most useful classification criterium for proteins is evolution (descent from a common ancestor), which requires both advanced phylogenetic methods and sensitive sequence search tools. To this end, we have developed a search tool, SENSER, which evolves almost entirely in homologous sequence space, yet has a performance comparable to the most advanced fold recognition methods. Using group II AAA ATPases as an example, we illustrate how hierarchical classification can yield profound insights into protein function and evolution. In particular we describe a rationale for the evolution of the RecA fold, which sheds light on the activation mechanism of helicases, ATP-dependent proteases, chaperones, and F1 ATPase, and we reconstruct an evolutionary pathway leading from a simple beta-alpha-beta-beta element found in transcription factors, via enzymes and chaperones, to aspartic proteinases.