Dating back to the late Early Cretaceous, the macrofossil record of the iconic lotus family (Nelumbonaceae) is one of the oldest of flowering plants and suggests that their unmistakable leaves and nutlets embedded in large pitted receptacular fruits evolved relatively little in the 100 million years since their first known appearance. Here we describe a new fossil from the late Barremian/Aptian Crato Formation flora (NE Brazil) with both vegetative and reproductive structures, Notocyamus hydrophobus gen. nov. et sp. nov., which is now the oldest and most complete fossil record of Nelumbonaceae. In addition, it displays a unique mosaic of ancestral and derived macro- and micromorphological traits that has never been documented before in this family. This new Brazilian fossil-species also provides a rare illustration of the potential morphological and anatomical transitions experienced by Nelumbonaceae prior to a long period of relative stasis. Its potential plesiomorphic and apomorphic features shared with Proteaceae and Platanaceae not only fill a major morphological gap within Proteales but also provide new support for their unexpected relationships first suggested by molecular phylogenies.