Greigite (Fe3S4) is a widespread authigenic magnetic mineral in anoxic sediments, and is also commonly biosynthesized by magnetotactic bacteria in aqueous environments. While the presence of fossilized bacterial magnetite (Fe3O4) has now been widely demonstrated, the preservation of greigite magnetofossils in the geological record is only poorly constrained. Here, we investigate Mio-Pliocene sediments of the former Black Sea to test whether we can detect greigite magnetofossils, and to unravel potential environmental controls on greigite formation. Our magnetic analyses and transmission electron microscope (TEM) observations indicate the presence of both diagenetic and bacterial greigite, and suggest a potentially widespread preservation of greigite magnetofossils in ancient sediments, which has important implications for assessing the reliability of paleomagnetic records carried by greigite. TEM-based chemical and structural analyses also indicate the common presence of nickel-substituted diagenetic iron sulfide crystals with a ferrimagnetic greigite structure. In addition, our cyclostratigraphic framework allows correlation of magnetic properties of Messinian former Black Sea sediments (Taman Peninsula, Russia) to global climate records. Diagenetic greigite enhancements appear to be climatically controlled, with greigite mainly occurring in warm/wet periods. Diagenetic greigite formation can be explained by variations in terrigenous inputs and dissolved pore water sulfate concentrations in different sedimentary environments. Our analysis demonstrates the usefulness of greigite for studying long-term climate variability in anoxic environments.