The presence of glue-like exopolymer produced by the marine benthic bacterium Alteromonas atlantica present in concentrations comparable with typical marine muds can enhance the yield stress of dilute clay-seawater suspensions typical of the sediment-water interface by 60%. This effect is inferred to be due mainly to bacterial attachment to and exopolymeric bridging between clay domains under nutrient-poor conditions. The relative change in the yield stress of a clay-seawater suspension, and by inference its erosion resistance, is dependent on the availability of nutrients and the history of microbial attachment. This conclusion applies regardless of the constitutive model used to describe the behavior of the suspension under shear. Our results are relevant to rheological studies of fine-particle suspensions in general because inevitable contamination of "abiotic" slurries often occurs under the very conditions (nutrient poor) that can result in maximal binding effects.