The ∼5.3-6.0 million-year-old evaporitic gypsum deposits of Cyprus and Crete contain a variety of stromatolites that formed during the Messinian salinity crisis. We recognize four stromatolite morphotypes, including domical, conical, columnar, and flat-laminated structures. Observations of morphological and textural variations among the different morphotypes reveal significant diversity and complexity in the nature of interactions between microorganisms, gypsum deposition, and gypsum crystal growth. Nonbiological processes (detrital gypsum deposition, in situ crust precipitation, syntaxial crystal growth, subsurface crystal growth, and recrystallization) interacted with inferred microbial processes (including localized growth of biofilms, trapping and binding of grains in mats, nucleation of gypsum on cells) to produce distinct morphological-textural assemblages. Evidence for biological origins is clear in some stromatolite morphotypes and can come from the presence of microfossils, the spatial distribution of organic matter, and stromatolite morphology. In one stromatolite morphotype, the presence of the stromatolite, or the biota associated with it, may have determined the morphology of gypsum crystals. In some stromatolite morphotypes, definitive evidence of a microbial influence is not as clear. There are broad similarities between the Messinian gypsum stromatolites and carbonate stromatolites elsewhere in the geologic record, such as the formation of precipitated and granular layers; the development of domed, columnar, and conical morphotypes; the potential for microbes to influence mineral precipitation; and the recrystallization of deposits during burial. However, in detail the array of microbial-sedimentary-diagenetic process interactions is quite distinct in gypsiferous systems due to differences in the way gypsum typically forms and evolves in the paleoenvironment compared to carbonate. Unique aspects of the taphonomy of gypsum compared to carbonate chemical sediments, generally speaking, include the following: the potential for growth of individual crystals to determine the shape of a stromatolite (and possibly vice versa), a more diverse set of outcomes relating to preservation versus destruction of textures through crystal growth and recrystallization, and a greater likelihood of preserving microfossils through encapsulation in large crystals. These insights gained from the study of terrestrial gypsum sedimentary rocks provide valuable guidance for the search for clues to past life in sulfate chemical sediments on Mars.