The relationship between the Chondrichthyes (cartilaginous fishes), the Actinopterygii (ray-finned fishes), and the piscine Sarcopterygii (lobe-finned fishes) and how the Tetrapoda (four-limbed terrestrial vertebrates) are related to these has been a contentious issue for more than a century. A general consensus about the relationship of these vertebrate clades has gradually emerged among morphologists, but no molecular study has yet provided conclusive evidence for any specific hypothesis. In order to examine these relationships on the basis of more extensive sequence data, we have produced almost 1,000,000 bp of expressed sequence tags (ESTs) from the African marbled lungfish, Protopterus aethiopicus. This new data set yielded 771 transcribed nuclear sequences that had not been previously described. The lungfish EST sequences were combined with EST data from two cartilaginous fishes and whole genome data from an agnathan, four ray-finned fishes, and four tetrapods. Phylogenomic analysis of these data yielded, for the first time, significant maximum likelihood support for a traditional gnathostome tree with a split between the Chondrichthyes and remaining (bone) gnathostomes. Also, the sister group relationship between Dipnoi (lungfishes) and Tetrapoda received conclusive support. Previously proposed hypotheses, such as the monophyly of fishes, could be rejected significantly. The divergence time between lungfishes and tetrapods was estimated to 382-388 Ma by the current data set and six calibration points.