Myxozoans are a diverse group of microscopic endoparasites that have been the focus of much controversy regarding their phylogenetic position. Two dramatically different hypotheses have been put forward regarding the placement of Myxozoa within Metazoa. One hypothesis, supported by ribosomal DNA (rDNA) data, place Myxozoa as a sister taxon to Bilateria. The alternative hypothesis, supported by phylogenomic data and morphology, place Myxozoa within Cnidaria. Here, we investigate these conflicting hypotheses and explore the effects of missing data, model choice, and inference methods, all of which can have an effect in placing highly divergent taxa. In addition, we identify subsets of the data that most influence the placement of Myxozoa and explore their effects by removing them from the data sets. Assembling the largest taxonomic sampling of myxozoans and cnidarians to date, with a comprehensive sampling of other metazoans for 18S and 28S nuclear rDNA sequences, we recover a well-supported placement of Myxozoa as an early diverging clade of Bilateria. By conducting parametric bootstrapping, we find that the bilaterian placement of Buddenbrockia could not alone be explained by long-branch attraction. After trimming a published phylogenomic data set, to circumvent problems of missing data, we recover the myxozoan Buddenbrockia plumatellae as a medusozoan cnidarian. In further explorations of these data sets, we find that removal of just a few identified sites under a maximum likelihood criterion employing the Whelan and Goldman amino acid substitution model changes the placement of Buddenbrockia from within Cnidaria to the alternative hypothesis at the base of Bilateria. Under a Bayesian criterion employing the CAT model, the cnidarian placement is more resilient to data removal, but under one test, a well-supported early diverging bilaterian position for Buddenbrockia is recovered. Our results confirm the existence of two relatively stable placements for myxozoans and demonstrate that conflicting signal exists not only between the two types of data but also within the phylogenomic data set. These analyses underscore the importance of careful model selection, taxon and data sampling, and in-depth data exploration when investigating the phylogenetic placement of highly divergent taxa.