The origin of land vertebrates was one of the major transitions in the history of vertebrates. Yet, despite many studies that are based on either morphology or molecules, the phylogenetic relationships among tetrapods and the other two living groups of lobe-finned fishes, the coelacanth and the lungfishes, are still unresolved and debated. Knowledge of the relationships among these lineages, which originated back in the Devonian, has profound implications for the reconstruction of the evolutionary scenario of the conquest of land. We collected the largest molecular data set on this issue so far, about 3,500 base pairs from seven species of the large 28S nuclear ribosomal gene. All phylogenetic analyses (maximum parsimony, neighbor-joining, and maximum likelihood) point toward the hypothesis that lungfishes and coelacanths form a monophyletic group and are equally closely related to land vertebrates. This evolutionary hypothesis complicates the identification of morphological or physiological preadaptations that might have permitted the common ancestor of tetrapods to colonize land. This is because the reconstruction of its ancestral conditions would be hindered by the difficulty to separate uniquely derived characters from shared derived characters in the coelacanth/lungfish and tetrapod lineages. This molecular phylogeny aids in the reconstruction of morphological evolutionary steps by providing a framework; however, only paleontological evidence can determine the sequence of morphological acquisitions that allowed lobe-finned fishes to colonize land.