Conventional wisdom suggests that bilateral organisms arose from ancestors that were radially, rather than bilaterally, symmetrical and, therefore, had a single body axis and no mesoderm. The two main hypotheses on how this transformation took place consider either a simple organism akin to the planula larva of extant cnidarians or the acoel Platyhelminthes (planuloid-acoeloid theory), or a rather complex organism bearing several or most features of advanced coelomate bilaterians (archicoelomate theory). We report phylogenetic analyses of bilaterian metazoans using quantitative (ribosomal, nuclear and expressed sequence tag sequences) and qualitative (HOX cluster genes and microRNA sets) markers. The phylogenetic trees obtained corroborate the position of acoel and nemertodermatid flatworms as the earliest branching extant members of the Bilateria. Moreover, some acoelomate and pseudocoelomate clades appear as early branching lophotrochozoans and deuterostomes. These results strengthen the view that stem bilaterians were small, acoelomate/pseudocoelomate, benthic organisms derived from planuloid-like organisms. Because morphological and recent gene expression data suggest that cnidarians are actually bilateral, the origin of the last common bilaterian ancestor has to be put back in time earlier than the cnidarian-bilaterian split in the form of a planuloid animal. A new systematic scheme for the Bilateria that includes the Cnidaria is suggested and its main implications discussed.