Shewanella spp. possess a broad respiratory versatility, which contributes to the occupation of hypoxic and anoxic environmental or host-associated niches. Here, we observe a strain-specific induction of biofilm formation in response to supplementation with the anaerobic electron acceptors dimethyl sulfoxide (DMSO) and nitrate in a panel of Shewanella algae isolates. The respiration-driven biofilm response is not observed in DMSO and nitrate reductase deletion mutants of the type strain S. algae CECT 5071, and can be restored upon complementation with the corresponding reductase operon(s) but not by an operon containing a catalytically inactive nitrate reductase. The distinct transcriptional changes, proportional to the effect of these compounds on biofilm formation, include cyclic di-GMP (c-di-GMP) turnover genes. In support, ectopic expression of the c-di-GMP phosphodiesterase YhjH of Salmonella Typhimurium but not its catalytically inactive variant decreased biofilm formation. The respiration-dependent biofilm response of S. algae may permit differential colonization of environmental or host niches.