Common bean (Phaseolus vulgaris L.) fixes atmospheric nitrogen (N2) through symbiotic nitrogen fixation (SNF) at levels lower than other grain legume crops. An understanding of the genes and molecular mechanisms underlying SNF will enable more effective strategies for the genetic improvement of SNF traits in common bean. In this study, transcriptome profiling was used to identify genes and molecular mechanisms underlying SNF differences between two common bean recombinant inbred lines that differed in their N-fixing abilities. Differential gene expression and functional enrichment analyses were performed on leaves, nodules and roots of the two lines when grown under N-fixing and non-fixing conditions. Receptor kinases, transmembrane transporters, and transcription factors were among the differentially expressed genes identified under N-fixing conditions, but not under non-fixing conditions. Genes up-regulated in the stronger nitrogen fixer, SA36, included those involved in molecular functions such as purine nucleoside binding, oxidoreductase and transmembrane receptor activities in nodules, and transport activity in roots. Transcription factors identified in this study are candidates for future work aimed at understanding the functional role of these genes in SNF. Information generated in this study will support the development of gene-based markers to accelerate genetic improvement of SNF in common bean.