A recently improved understanding of gut immunity has merged with current thinking in biological and medical science, pointing to an apparent function of the mammalian cecal appendix as a safe-house for symbiotic gut microbes, preserving the flora during times of gastrointestinal infection in societies without modern medicine. This function is potentially a selective force for the evolution and maintenance of the appendix, and provides an impetus for reassessment of the evolution of the appendix. A comparative anatomical approach reveals three apparent morphotypes of the cecal appendix, as well as appendix-like structures in some species that lack a true cecal appendix. Cladistic analyses indicate that the appendix has evolved independently at least twice (at least once in diprotodont marsupials and at least once in Euarchontoglires), shows a highly significant (P < 0.0001) phylogenetic signal in its distribution, and has been maintained in mammalian evolution for 80 million years or longer.