For the first time the phylogenetic relationships of early eureptiles, consisting of captorhinids, diapsids, and protorothyridids, are investigated in a modern phylogenetic context using both parsimony and Bayesian approaches. Ninety parsimony-informative characters and 25 taxa were included in the analyses. The Bayesian analysis was run with and without a gamma-shape parameter allowing for variable rates across characters. In addition, we ran two more Bayesian analyses that included 42 autapomorphies and thus parsimony-uninformative characters in order to test the effect of variable branch lengths. The different analyses largely converged to the same topology, suggesting that the "protorothyridid" Coelostegus is the sister taxon of all other eureptiles and that the remaining "protorothyridids" are paraphyletic. Also, there is a close relationship between diapsids and Anthracodromeus, Cephalerpeton, and Protorothyris, a grouping of Thuringothyris with captorhinids, and a variable position of the "protorothyridids" Brouffia, Hylonomus, and Paleothyris. The lack of resolution in some parts of the tree might be due to "hard polytomies" and short divergence times between the respective taxa. The tree topology is consistent with the hypothesis that the temporal fenestrations of diapsid reptiles appear to be the consequence of a more lightly built skeleton, indicating a significant ecological shift in the early stages of diapsid evolution. Bayesian analysis is a very useful additional approach in studies of fossil taxa in which more traditional statistical support like the bootstrap is often weak. However, the exclusive use of the Mk model appears suitable only if autapomorphic characters are included, whereas the Mk+gamma model performed well with or without autapomorphies.