The interaction between rhizobia and their legume host plants conduces to the formation of specialized root organs called nodules where rhizobia differentiate into bacteroids which fix atmospheric nitrogen to the benefit of the plant. This beneficial symbiosis is of importance in the context of sustainable agriculture as legumes do not require the addition of nitrogen fertilizer to grow. Interestingly, nitric oxide (NO) has been detected at various steps of the rhizobium–legume symbiosis where it has been shown to play multifaceted roles. Both bacterial and plant partners are involved in NO synthesis in nodules. To better understand the role of NO, and in particular the role of bacterial NO, at all steps of rhizobia–legumes interaction, the enzymatic sources of NO have to be elucidated. In this review, we discuss different enzymatic reactions by which rhizobia may potentially produce NO. We argue that there is most probably no NO synthase activity in rhizobia, and that instead the NO2− reductase nirK, which is part of the denitrification pathway, is the main bacterial source of NO. The nitrate assimilation pathway might contribute to NO production but only when denitrification is active. The different approaches to measure NO in rhizobia are also addressed.