During the Cenozoic, the Arabian Plate separated from continental Africa and assumed a closer geographical relationship with Eurasia. As such, the vertebrate fossil record of the Arabian Peninsula has great potential for documenting faunal interchanges that occurred as a result of such tectonic events, with a shift from a primarily Afro-Arabian fauna in the Palaeogene to a more cosmopolitan fauna in the Neogene. Understanding of the sequence and timing of this faunal interchange has long been hampered by a lack of palaeontological data. Recently recovered fossils from the Middle Eocene Kaninah Formation of Yemen constitute the earliest Palaeogene record of continental vertebrates from the Arabian Peninsula, thereby offering a rare glimpse at the region's post- -Cretaceous fauna. Here we describe fossil materials from the Kaninah Formation, a collection of dental and postcranial elements representing a mesoeucrocodylian crocodyliform of unclear affinities. The specimen exhibits ziphodont tooth morphology along with a biserial paravertebral shield and polygonal gastral osteoderms, consistent with certain mesoeucrocodylians (e.g., ziphodontan notosuchians). Yet the associated fragmentary anterior caudal vertebra, although badly abraded, preserves morphology suggestive of procoely. This vertebral type in combination with the dental and osteoderm morphology is much more taxonomically restrictive and consistent with the suite of characters exhibited by atoposaurids, a finding that would significantly extend that clade through the Cretaceous/Palaeogene boundary. Alternatively, given the relative paucity of information from the region during the Palaeogene, the combination of characteristics of the Kaninah crocodyliform may reflect a novel or poorly known form exhibiting previously unrecognised character mosaicism. We take a conservative approach, and refer the Kaninah specimen to Mesoeucrocodylia, Atoposauridae (?) pending discovery of more complete material. New fossils recovered from the Kaninah Formation raise unanticipated questions about the longevity of Mesozoic clades, underscoring the role that the region may play in revealing novel occurrences, relictual forms, and evidence of faunal dispersals from this critical interval in vertebrate evolutionary history.