The phylogeny of the Bilateria and especially the early steps in the evolution of the bilaterian bauplan are still a controversial topic. In this context the relationships of the platyhelminths and the nematodes play a crucial role. Previous molecular studies of the relationships of these groups, which were based on 18S ribosomal DNA sequences, yielded conflicting results. In the present study a new framework is developed for the phylogenetic analysis of bilaterian relationships, using concatenated amino acid sequences of several nuclear genes. In this analysis, the rhabditophoran platyhelminths are probably the sister group of all other analyzed Bilateria, the Eubilateria, which are characterized by a one-way intestine with an anus. The Eubilateria are split into the nematode lineage and the coelomates. The phylogenetic results of the present study indicate that genetic features found in the model organisms Caenorhabditis and Drosophila might be found in all Eubilateria. Estimations of the divergence times show that the major bilaterian phyla did not originate in an explosive radiation during the Cambrian but rather that the Bilateria have a several hundred million years long Precambrian history.