We used new 18S and 28S rRNA sequences analysed with parsimony, maximum likelihood and Bayesian methods of phylogenetic reconstruction to show that Nemertodermatida, generally classified as the sister group of Acoela within the recently proposed Phylum Acoelomorpha, are a separate basal bilaterian lineage. We used several analytical approaches to control for possible long branch attraction (LBA) artefacts in our results. Parsimony and the model based phylogenetic reconstruction methods that incorporate ‘corrections’ for substitution rate heterogenities yielded concordant results. When putative long branch taxa were experimentally removed the resulting topologies were consistent with our total evidence analysis. Deletion of fast-evolving nucleotide sites decreased resolution and clade support, but did not support a topology conflicting with the total evidence analysis. Establishment of Acoela and Nemertodermatida as two early lineages facilitates reconstruction of ancestral bilaterian features. The ancestor of extant Bilateria was a small, benthic direct developer without coelom or a planktonic larval stage. The previously proposed Phylum Acoelomorpha is dismissed as paraphyletic.