The thick gypsum deposits formed in the Mediterranean Basin during the Messinian salinity crisis incorporate dense mazes of filamentous fossils, which were interpreted as algae or cyanobacteria, thus pointing to a shallow-marine subtidal or intertidal environment. The data presented here reveal that these filaments represent remains of colorless, vacuolated sulfide-oxidizing bacteria. This interpretation is supported by the presence of small crystal aggregates of iron sulfide (pyrite) and associated polysulfide within the filamentous fossils. Pyrite and polysulfide are considered to result from early diagenetic transformation of original zero-valent sulfur globules stored within the cells, which is a clade-diagnostic feature of living and degraded sulfur bacteria. In addition to filamentous fossils, the studied gypsum crystals contain remains of euryhaline and stenohaline diatoms and clay-rich aggregates interpreted as alteration products of marine snow floccules. This peculiar fossil assemblage reflects conditions of increased productivity in the water column, triggered by high fluxes of nutrients into the basin during phases of enhanced riverine runoff and freshwater discharge. This study confirms that gypsum evaporites have great potential to preserve the early stages of the taphonomic alteration of bacterial cells, shedding light on the paleoecology of ancient hypersaline environments.