A series of recent studies recovered consistent phylogenetic scenarios of jawed vertebrates, such as the paraphyly of placoderms with respect to crown gnathostomes, and antiarchs as the sister group of all other jawed vertebrates. However, some of the phylogenetic relationships within the group have remained controversial, such as the positions of Entelognathus, ptyctodontids, and the Guiyu-lineage that comprises Guiyu, Psarolepis and Achoania. The revision of the dataset in a recent study reveals a modified phylogenetic hypothesis, which shows that some of these phylogenetic conflicts were sourced from a few inadvertent miscodings. The interrelationships of early gnathostomes are addressed based on a combined new dataset with 103 taxa and 335 characters, which is the most comprehensive morphological dataset constructed to date. This dataset is investigated in a phylogenetic context using maximum parsimony (MP), Bayesian inference (BI) and maximum likelihood (ML) approaches in an attempt to explore the consensus and incongruence between the hypotheses of early gnathostome interrelationships recovered from different methods. Our findings consistently corroborate the paraphyly of placoderms, all 'acanthodians' as a paraphyletic stem group of chondrichthyans, Entelognathus as a stem gnathostome, and the Guiyu-lineage as stem sarcopterygians. The incongruence using different methods is less significant than the consensus, and mainly relates to the positions of the placoderm Wuttagoonaspis, the stem chondrichthyan Ramirosuarezia, and the stem osteichthyan Lophosteus-the taxa that are either poorly known or highly specialized in character complement. Given that the different performances of each phylogenetic approach, our study provides an empirical case that the multiple phylogenetic analyses of morphological data are mutually complementary rather than redundant.