Metazoan phylogeny remains one of evolutionary biology's major unsolved problems. Molecular and morphological data, as well as different analytical approaches, have produced highly conflicting results due to homoplasy resulting from more than 570 million years of evolution. To date, parsimony has been the only feasible combined approach but is highly sensitive to long-branch attraction. Recent development of stochastic models for discrete morphological characters and computationally efficient methods for Bayesian inference has enabled combined molecular and morphological data analysis with rigorous statistical approaches less prone to such inconsistencies. We present the first statistically founded analysis of a metazoan data set based on a combination of morphological and molecular data and compare the results with a traditional parsimony analysis. Interestingly, the Bayesian analyses demonstrate a high degree of congruence between morphological and molecular data, and both data sets contribute to the result of the combined analysis. Additionally, they resolve several irregularities obtained in previous studies and show high credibility values for controversial groups such as the ecdysozoans and lophotrochozoans. Parsimony, on the contrary, shows conflicting results, with morphology being congruent to the Bayesian results and the molecular data set producing peculiarities that are largely reflected in the combined analysis.