Aldehyde oxidases (AOXs) and xanthine dehydrogenases (XDHs) belong to the family of molybdo-flavoenzymes. Although AOXs are not identifiable in fungi, these enzymes are represented in certain protists and the majority of plants and vertebrates. The physiological functions and substrates of AOXs are unknown. Nevertheless, AOXs are major drug metabolizing enzymes, oxidizing a wide range of aromatic aldehydes and heterocyclic compounds of medical/toxicological importance. Using genome sequencing data, we predict the structures of AOX genes and pseudogenes, reconstructing their evolution. Fishes are the most primitive organisms with an AOX gene (AOXα), originating from the duplication of an ancestral XDH. Further evolution of fishes resulted in the duplication of AOXα into AOXβ and successive pseudogenization of AOXα. AOXβ is maintained in amphibians and it is the likely precursors of reptilian, avian, and mammalian AOX1. Amphibian AOXγ is a duplication of AOXβ and the likely ancestor of reptilian and avian AOX2, which, in turn, gave rise to mammalian AOX3L1. Subsequent gene duplications generated the two mammalian genes, AOX3 and AOX4. The evolution of mammalian AOX genes is dominated by pseudogenization and deletion events. Our analysis is relevant from a structural point of view, as it provides information on the residues characterizing the three domains of each mammalian AOX isoenzyme. We cloned the cDNAs encoding the AOX proteins of guinea pig and cynomolgus monkeys, two unique species as to the evolution of this enzyme family. We identify chimeric RNAs from the human AOX3 and AOX3L1 pseudogenes with potential to encode a novel microRNA.