Paraburkholderia phymatum belongs to the β-subclass of proteobacteria. It has recently been shown to be able to nodulate and fix nitrogen in symbiosis with several mimosoid and papilionoid legumes. In contrast to the symbiosis of legumes with α-proteobacteria, very little is known about the molecular determinants underlying the successful establishment of this mutualistic relationship with β-proteobacteria. In this study, we performed an RNA-sequencing (RNA-seq) analysis of free-living P. phymatum growing under nitrogen-replete and -limited conditions, the latter partially mimicking the situation in nitrogen-deprived soils. Among the genes upregulated under nitrogen limitation, we found genes involved in exopolysaccharides production and in motility, two traits relevant for plant root infection. Next, RNA-seq data of P. phymatum grown under free-living conditions and from symbiotic root nodules of Phaseolus vulgaris (common bean) were generated and compared. Among the genes highly upregulated during symbiosis, we identified-besides the nif gene cluster-an operon encoding a potential cytochrome o ubiquinol oxidase (Bphy_3646-49). Bean root nodules induced by a cyoB mutant strain showed reduced nitrogenase and nitrogen fixation abilities, suggesting an important role of the cytochrome for respiration inside the nodule. The analysis of mutant strains for the RNA polymerase transcription factor RpoN (σ54) and its activator NifA indicated that-similar to the situation in α-rhizobia-P. phymatum RpoN and NifA are key regulators during symbiosis with P. vulgaris.