Legume rhizobium symbiosis is initiated upon perception of bacterial secreted lipo-chitooligosaccharides (LCOs). Perception of these signals by the plant initiates a signaling cascade that leads to nodule formation. Several studies have implicated a function for cytokinin in this process. However, whether cytokinin accumulation and subsequent signaling are an integral part of rhizobium LCO signaling remains elusive. Here, we show that cytokinin signaling is required for the majority of transcriptional changes induced by rhizobium LCOs. In addition, we demonstrate that several cytokinins accumulate in the root susceptible zone 3 h after rhizobium LCO application, including the biologically most active cytokinins, trans-zeatin and isopentenyl adenine. These responses are dependent on calcium- and calmodulin-dependent protein kinase (CCaMK), a key protein in rhizobial LCO-induced signaling. Analysis of the ethylene-insensitive Mtein2/Mtsickle mutant showed that LCO-induced cytokinin accumulation is negatively regulated by ethylene. Together with transcriptional induction of ethylene biosynthesis genes, it suggests a feedback loop negatively regulating LCO signaling and subsequent cytokinin accumulation. We argue that cytokinin accumulation is a key step in the pathway leading to nodule organogenesis and that this is tightly controlled by feedback loops.