The Messinian microbialites of the Terminal Carbonate Complex (TCC) from the Neogene basins of southeastern Spain show both diversified morphologies and an excellent preservation of primary microbial microstructures. Their stratigraphic architecture, fabric (micro-, meso-, and macro-fabric), and mineralogical composition were investigated in eight localities from three sedimentary basins of southeastern Spain: The Sorbas and Bajo Segura basins and the Agua Amarga depression. Two recurrent microbialite associations were distinguished. Laterally linked low relief stromatolites predominated in Microbialite Association 1 (MA1), which probably formed in low energy lagoons or lakes with fluctuating normal marine to hypersaline water. The microfabrics of MA1 reflected the predominance of microbially induced/influenced precipitation of carbonates and locally (Ca)-Mg-Al silicates. Microbialite Association 2 (MA2) developed in high energy wave and tidal influenced foreshore to shoreface, in normal marine to hypersaline water. High-relief buildups surrounded by mobile sediment (e.g., ooids or pellets) dominated in this environment. MA2 microbialites showed a significant proportion of thrombolitic mesofabric. Grain-rich microfabrics indicated that trapping and binding played a significant role in their accretion, together with microbially induced/influenced carbonate precipitation. The stratigraphic distribution of MA1 and MA2 was strongly influenced by water level changes, the morphology and nature of the substratum, and exposure to waves. MA1 favorably developed in protected areas during third to fourth order early transgression and regression phases. MA2 mostly formed during the late transgressions and early regressions in high energy coastal areas, often corresponding to fossil coral reefs. Platform scale syn-sedimentary gypsum deformation and dissolution enhanced microbial carbonate production, microbialites being thicker and more extended in zones of maximum deformation/dissolution. Microbial microstructures (e.g., microbial peloids) and microfossils were preserved in the microbialites. Dolomite microspheres and filaments showed many morphological similarities with some of the cyanobacteria observed in modern open marine and hypersaline microbialites. Dolomite potentially replaced a metastable carbonate phase during early diagenesis, possibly in close relationship with extracellular polymeric substances (EPS) degradation. Double-layered microspheres locally showed an inner coating made of (Ca)-Mg-Al silicates and carbonates. This mineral coating could have formed around coccoid cyanobacteria and indicated an elevated pH in the upper part of the microbial mats and a potential dissolution of diatoms as a source of silica. Massive primary dolomite production in TCC microbialites may have resulted from enhanced sulfate reduction possibly linked to the dissolving gypsum that would have provided large amounts of sulfate-rich brines to microbial mats. Our results open new perspectives for the interpretation of ancient microbialites associated with major evaporite deposits, from microbe to carbonate platform scales.