The fossil record of storks (Aves, Ciconiidae) includes a relatively large number of specimens from the Middle Eocene onwards, but no taxon is as well represented as Grallavis edwardsi form the Early Miocene of the Allier region in central France. Despite this, the phylogenetic placement of G. edwardsi among other storks has remained elusive not least because of the lack of a robust phylogenetic framework for living storks. To find out how G. edwardsi relates to recent Ciconiidae, we performed a phylogenetic analysis based on osteological features including all living genus-level taxa of the Ciconiidae. We show that the previously reported similarities to the extant taxa Ephippiorhynchus and Jabiru are based on plesiomorphic features, and our analysis supports a sister group relationship between Grallavis edwardsi and Leptoptilos. Our results are also consistent with a basal divergence within Ciconiidae between Mycteria and Anastomus, which are among the smallest storks, and all other storks. A sister group relationship between storks of the genus Ciconia and all large storks (Leptoptilini) is recovered albeit with weak support, which may be due to homoplastic features linked to their large size. Grallavis edwardsi possessed several osteological adaptations suited for scavenging, and despite lacking some derived traits characteristic of Leptoptilos, it is likely to have been a precursor of large marabou and adjutant storks.