Cytokinin and nitric oxide (NO) have been characterized as signaling molecules to trigger cell division in tissue culture. Here, we show that the hypocotyl and root explants of Arabidopsis NO-deficient mutant nos1/noa1 exhibit severe defects in callus induction and shoot regeneration in response to cytokinin. Accordingly, depletion of NO caused by a NO scavenger leads to a severe inhibitory effect on callus induction. Moreover, cytokinin-induced NO production is impaired in nos1/noa1 in which cytokinin-triggered activation of cell cycle gene CYCD3;1 is inhibited, indicating that NO may act downstream of cytokinin in the control of cell proliferation through CYCD3;1. This hypothesis is further confirmed by the genetic evidence that constitutive expression of CYCD3;1 complements the defects of nos1/noa1 mutant in meristematic activity in shoot, root, and floral tissues as well as in cytokinin-induced callus initiation and shoot regeneration. Furthermore, we show that NO deficiency caused by loss of NOS1/NOA1 impairs cellular development such as the duration of the mitotic phase and timing of the transition to endocycles in nos1/noa1 mutant leaves, which can be reverted by constitutive expression of CYCD3;1. Taken together, these results demonstrate that NO mediates transcriptional activation of CYCD3;1 in regulating the mitotic cycles in response to cytokinins.