We present a redescription of Megalocoelacanthus dobiei, a giant fossil coelacanth from Upper Cretaceous strata of North America. Megalocoelacanthus has been previously described on the basis of composite material that consisted of isolated elements. Consequently, many aspects of its anatomy have remained unknown as well as its phylogenetic relationships with other coelacanths. Previous studies have suggested that Megalocoelacanthus is closer to Latimeria and Macropoma than to Mawsonia. However, this assumption was based only on the overall similarity of few anatomical features, rather than on a phylogenetic character analysis. A new, and outstandingly preserved specimen from the Niobrara Formation in Kansas allows the detailed description of the skull of Megalocoelacanthus and elucidation of its phylogenetic relationships with other coelacanths. Although strongly flattened, the skull and jaws are well preserved and show many derived features that are shared with Latimeriidae such as Latimeria, Macropoma and Libys. Notably, the parietonasal shield is narrow and flanked by very large, continuous vacuities forming the supraorbital sensory line canal. Such an unusual morphology is also known in Libys. Some other features of Megalocoelacanthus, such as its large size and the absence of teeth are shared with the mawsoniid genera Mawsonia and Axelrodichthys. Our cladistic analysis supports the sister-group relationship of Megalocoelacanthus and Libys within Latimeriidae. This topology suggests that toothless, large-sized coelacanths evolved independently in both Latimeriidae and Mawsoniidae during the Mesozoic. Based on previous topologies and on ours, we then review the high-level taxonomy of Latimerioidei and propose new systematic phylogenetic definitions.