The clownfish-sea anemone symbiosis has been a model system for understanding fundamental evolutionary and ecological processes. However, our evolutionary understanding of this symbiosis comes entirely from studies of clownfishes. A holistic understanding of a model mutualism requires systematic, biogeographic, and phylogenetic insight into both partners. Here, we conduct the largest phylogenetic analysis of sea anemones (Order Actiniaria) to date, with a focus on expanding the biogeographic and taxonomic sampling of the 10 nominal clownfish-hosting species. Using a combination of mtDNA and nuDNA loci we test (1) the monophyly of each clownfish-hosting family and genus, (2) the current anemone taxonomy that suggests symbioses with clownfishes evolved multiple times within Actiniaria, and (3) whether, like the clownfishes, there is evidence that host anemones have a Coral Triangle biogeographic origin. Our phylogenetic reconstruction demonstrates widespread poly- and para-phyly at the family and genus level, particularly within the family Stichodactylidae and genus Stichodactyla, and suggests that symbioses with clownfishes evolved minimally three times within sea anemones. We further recover evidence for a Tethyan biogeographic origin for some clades. Our data provide the first evidence that clownfish and some sea anemone hosts have different biogeographic origins, and that there may be cryptic species of host anemones. Finally, our findings reflect the need for a major taxonomic revision of the clownfish-hosting sea anemones.