Molecular phylogenetics has rapidly established the evolutionary positions of most major mammal groups, yet analyses have repeatedly failed to agree on that of bats (order Chiroptera). Moreover, the relationship among the major bat lineages has proven equally contentious, with ongoing disagreements about whether echolocating bats are paraphyletic or a true group having profound implications for whether echolocation evolved once or possibly multiple times. By generating new bat genome data and applying model-based phylogenomic analyses designed to accommodate heterogeneous evolutionary processes, we show that-contrary to recent suggestions-bats are not closely related to odd-toed ungulates but instead have a more ancient origin as sister group to a large clade of carnivores, ungulates, and cetaceans. Additionally, we provide the first genome-scale support showing that laryngeal echolocating bats are not a true group and that this paraphyly is robust to their position within mammals. We suggest that earlier disagreements in the literature may reflect model misspecification, long-branch artifacts, poor taxonomic coverage, and differences in the phylogenetic markers used. These findings are a timely reminder of the relevance of experimental design and careful statistical analysis as we move into the phylogenomic era.