Enigmatic, thick-walled, agglutinated microfossils are described for the first time from the Middle Miocene of Austria. The microfossils are documented in large numbers from the Oberpullendorf Basin in Austria, where they occur in intertidal mudflat deposits associated with an oyster biostrome and in close vicinity to stromatolites. The basin was part of the epicontinental Central Paratethys Sea and was covered by a warm, restricted, hypersaline lagoon, which formed during the Badenian Salinity Crisis at roughly 13.8–13.6 Ma. Widespread evaporite formation characterized the Central Paratethys Sea at that time. Micro-CT scans of the structures reveal morphological features, which suggests that the fossils are rhizoliths, most likely from the rhizolith type 1. The fossils were probably formed by halophilic grasses, or herbaceous plants. The rhizoliths are strikingly similar to agglutinated foraminifera of the family Astrorhizidae and could easily be confused with foraminifera. Extant Astrorhizidae, however, are typically found in offshore deep-sea environments, which is in strong contrast to the ecological requirements of the Miocene Ritzing microfossils. Therefore, despite the morphological similarities, a relation with Astrorhizidae is excluded. We provide the first detailed morphologic description of fossil rhizoliths from a hypersaline lagoon and assume that they might represent an overlooked feature in coastal deposits of the Proto-Mediterranean Sea and the Paratethys region.