Neocheilostomes possessing ovicells for larval brooding originated in the late Albian and radiated explosively in the Late Cretaceous. Our understanding of this radiation is hampered by poor knowledge of the taxonomy of the earliest neocheilostomes. Here we describe a new neocheilostome genus, Ehrhardina, from shallow-water sediments in the early Cenomanian of Western Europe. Two species (Ehrhardina voigti sp. nov. and E. pikeae sp. nov.) are referred to the new genus. Ehrhardina gen. nov. is an onychocellid characterized by large opesiae with proximolateral, symmetrical opesiular constrictions and proximolateral, long opesiular indentations, bilaterally symmetrical interzooidal avicularia and lacking spine bases, but with hyperstomial ovicells that have ectooecia formed of exterior wall calcification. Colonies are unusually large for encrusting onychocellids and multilaminar; ovicells are primitive in showing a median suture in the ectooecium. Similarities between Ehrhardina gen. nov. and Aechmella, Floridina, Floridinella, and Onychocella are discussed, and a key for the discrimination of these genera is provided. Ehrhardina gen. nov. is the oldest neocheilostome known to construct large, multilaminar colonies.