BACKGROUND: The subclass Enoplia (Phylum Nematoda) is purported to be the earliest branching clade amongst all nematode taxa, yet the deep phylogeny of this important lineage remains elusive. Free-living marine species within the order Enoplida play prominent roles in marine ecosystems, but previous molecular phylogenies have provided only the briefest evolutionary insights; this study aimed to firmly resolve internal relationships within the hyper-diverse but poorly understood Enoplida. In addition, we revisited the molecular framework of the Nematoda using a rigorous phylogenetic approach in order to investigate patterns of early splits amongst the oldest lineages (Dorylaimia and Enoplia). RESULTS: Morphological identifications, nuclear gene sequences (18S and 28S rRNA), and mitochondrial gene sequences (cox1) were obtained from marine Enoplid specimens representing 37 genera. The 18S gene was used to resolve deep splits within the Enoplia and evaluate the branching order of major clades in the nematode tree; multiple phylogenetic methods and rigorous empirical tests were carried out to assess tree topologies under different parameters and combinations of taxa. Significantly increased taxon sampling within the Enoplida resulted in a well-supported, robust phylogenetic topology of this group, although the placement of certain clades was not fully resolved. Our analysis could not unequivocally confirm the earliest splits in the nematode tree, and outgroup choice significantly affected the observed branching order of the Dorylaimia and Enoplia. Both 28S and cox1 were too variable to infer deep phylogeny, but provided additional insight at lower taxonomic levels. CONCLUSIONS: Analysis of internal relationships reveals that the Enoplia is split into two main clades, with groups consisting of terrestrial (Triplonchida) and primarily marine fauna (Enoplida). Five independent lineages were recovered within the Enoplida, containing a mixture of marine and terrestrial species; clade structure suggests that habitat transitions have occurred at least four times within this group. Unfortunately, we were unable to obtain a consistent or well-supported topology amongst early-branching nematode lineages. It appears unlikely that single-gene phylogenies using the conserved 18S gene will be useful for confirming the branching order at the base of the nematode tree-future efforts will require multi-gene analyses or phylogenomic methods.