The sedges (family Cyperaceae) are an economically and ecologically important monocot group dating back at least to the Paleocene. While modern genera are mostly unknown before the Oligocene, several extinct taxa are recognized as the earliest sedges. Their affinities have been unclear until now, because they are found as isolated, often abraded fruits or endocarps. Exceptionally preserved sedge fossils from the Middle Eocene of Messel, Germany yield more characters for identification. Fossil cyperacean infructescences with in situ pollen are recognized for the first time and show features of the early-divergent mapanioid sedges. Pollen resembles that of tribe Hypolytreae. Comparisons with extant taxa suggest the closest affinities with Hypolytrum and Mapania. However, the Messel fossils represent a distinct taxon, Volkeria messelensis gen. et sp. nov. Without the additional characters of infructescence and pollen, the Messel fruits would have been placed in the extinct genus Caricoidea, a typical Eocene sedge that was widespread across Eurasia. Similarities of fruit structure suggest that Caricoidea was also a mapanioid sedge. Mapanioid sedges are found today in tropical wet forests and swamps, a distribution suggesting that early sedges occupied a similar habitat, unlike many modern sedges, and were not precursors to open grassland vegetation.