The dichotomy within Amniota (mammals and reptiles) was recognized early in the history of phylogenetic systematics, and with it developed a canonical understanding of the evolutionary relationships of early-diverging clades. In recent years, the relationships of these clades have shifted dramatically among studies, which has profound effects on how researchers interpret evolutionary patterns in early amniotes. To gain a fuller understanding of the early evolution of amniotes, we compiled the largest amniote-wide phylogenetic dataset to date, including 590 fully illustrated characters and 150 taxa representing all the major clades of “pelycosaurian” stem mammals, pan-reptiles, and several outgroups. We analyzed this dataset under Bayesian and parsimony frameworks, which resulted in different topologies, particularly among stem mammals and near-crown and within-crown Reptilia. To explore the effect sampling has on tree topology, we conducted three series of exclusion experiments, each consisting of ten analyses, each with ten fewer taxa than the previous, as well as 26 exclusion analyses removing one clade or individual at a time. This experiment showed that taxon sampling has a major effect on early amniote tree topology, and many of the topologies recovered bear striking similarities to those reported in recent publications. Furthermore, we identify and discuss several unique effects that taxon exclusion may have on phylogenies. To address poorly resolved (i.e., polytomies) and unstable portions of amniote phylogeny, where branches frequently move or dismantle depending on sampling and choice of analytical technique, we encourage more detailed anatomical work on early amniotes, particularly stem mammals.