Cyclic di-GMP (c-di-GMP) is a secondary messenger that controls a variety of cellular processes, including the switch between a biofilm and a planktonic bacterial lifestyle. This nucleotide binds to cellular effectors in order to exert its regulatory functions. In Salmonella, two proteins, BcsA and YcgR, both of them containing a c-di-GMP binding PilZ domain, are the only known c-di-GMP receptors. BcsA, upon c-di-GMP binding, synthesizes cellulose, the main exopolysaccharide of the biofilm matrix. YcgR is dedicated to c-di-GMP-dependent inhibition of motility through its interaction with flagellar motor proteins. However, previous evidences indicate that in the absence of YcgR, there is still an additional element that mediates motility impairment under high c-di-GMP levels. Here we have uncovered that cellulose per se is the factor that further promotes inhibition of bacterial motility once high c-di-GMP contents drive the activation of a sessile lifestyle. Inactivation of different genes of the bcsABZC operon, mutation of the conserved residues in the RxxxR motif of the BcsA PilZ domain, or degradation of the cellulose produced by BcsA rescued the motility defect of ΔycgR strains in which high c-di-GMP levels were reached through the overexpression of diguanylate cyclases. High c-di-GMP levels provoked cellulose accumulation around cells that impeded flagellar rotation, probably by means of steric hindrance, without affecting flagellum gene expression, exportation, or assembly. Our results highlight the relevance of cellulose in Salmonella lifestyle switching as an architectural element that is both essential for biofilm development and required, in collaboration with YcgR, for complete motility inhibition.