The evolutionary relationships of gnathostomes (jawed vertebrates), which comprise chondrichthyans (cartilaginous fishes), lobe-finned fishes (coelacanths and lungfishes), tetrapods, and actinopterygians (ray-finned fishes), have been debated for almost a century. Phylogenetic analyses based on fossils, morphology, and molecular sequences have generated different models of relationships that remain unresolved. We identified 13 derived shared molecular markers (synapomorphies) that define clades in the vertebrate lineage and used them to resolve the phylogenetic relationships of extant jawed vertebrates. Our markers include the presence or absence of insertions and deletions in coding sequences, nuclear introns, and alternatively spliced transcripts. The synapomorphies identified by us are congruent with each other and give rise to a single phylogenetic tree. This tree confirms that chondrichthyans are basal to all living gnathostomes, that lungfishes (Dipnoi) are the closest living relatives of tetrapods, and that bichirs (Cladistia) are the living members of the most ancient family of ray-finned fishes. Our study also provides molecular evidence to support the monophyly of living tetrapods and teleosts.