In bacteria, intracellular amounts of the signal molecule cyclic di-GMP (c-di-GMP) are determined by biosynthetic enzymes, or diguanylate cyclases (DGCs), and degradative enzymes, or c-di-GMP phosphodiesterases (c-PDEs). In Escherichia coli, the production of curli fibers, an important adhesion factor, responds to c-di-GMP. The yddV-dos operon, which encodes a DGC and a c-PDE acting as a protein complex, is highly expressed at a low growth temperature and in the stationary phase, i.e. conditions that also stimulate curli production. We show that perturbations in the balance between YddV and Dos, obtained either through inactivation of the yddV gene or through overproduction of either YddV or Dos, strongly affect curli production. Both YddV and Dos proteins regulate the transcription of the csgBAC operon, which encodes curli structural subunits, while not affecting the expression of the regulatory operon csgDEFG. Consistent with the role of both YddV and Dos proteins as oxygen sensors, their effects on csgBAC gene expression were dramatically reduced in cells grown under anoxic conditions. Our results show that the yddV-dos operon plays an important role in the expression of curli-encoding genes in aerobically growing E. coli, and suggest that YddV and Dos, through their opposite activities, might finely tune curli production in response to oxygen availability.