NAD(H)-binding proteins play important roles in cell-cycle and developmental signaling in eukaryotes. We identified a bifunctional NAD(H)-binding regulator (KidO) that integrates cell-fate signaling with cytokinesis in the bacterium Caulobacter crescentus. KidO stimulates the DivJ kinase and directly acts on the cytokinetic tubulin, FtsZ, to tune cytokinesis with the cell cycle. At the G1-->S transition, DivJ concomitantly signals the ClpXP-dependent degradation of KidO and CtrA, a cell-cycle transcriptional regulator/DNA replication inhibitor. This proteolytic event directs KidO and CtrA into oscillatory cell-cycle abundance patterns that coordinately license replication and cytokinesis. KidO resembles NAD(P)H-dependent oxidoreductases, and conserved residues in the KidO NAD(H)-binding pocket are critical for regulation of FtsZ, but not for DivJ. Since NADPH-dependent regulation by a KidO-like oxidoreductase also occurs in humans, organisms from two domains of life exploit the enzymatic fold of an ancestral oxidoreductase potentially to coordinate cellular or developmental activities with the availability of the metabolic currency, NAD(P)H.