Rhizobia in root nodules benefit their host by fixing atmospheric N2 to NH3. In return they receive carbon which they use to reproduce inside the nodule. They also store energy in the lipid polyhydroxybutyrate (PHB) which could, in theory, be used later to support either N2 fixation or reproduction. Previous work has demonstrated a tradeoff between N2 fixation and PHB accumulation. Therefore, if PHB enhances rhizobium fitness, less-mutualistic cheaters should be favored by natural selection relative to strains fixing large amounts of N2. High and low-PHB populations (a 2.6-fold difference) of genetically uniform rhizobia were generated by fractionating stationary phase Sinorhizobium meliloti via density gradient centrifugation. These cells were starved for 150 days in carbon-free growth media. During starvation both populations showed net reproduction, however the high-PHB population attained a maximum of 2.4x its initial population size while the low-PHB population only obtained a 1.3x increase. Qualitatively similar results were found when culture-based methods were used to generate high and low-PHB populations. We also examined the effect of PHB on competition for nodulation. Both wildtype and PHB(-) mutant rhizobia formed similar numbers of nodules when inoculated alone, yet wildtype rhizobia completely excluded PHB(-) mutants from nodules when competed at equal densities. Stored PHB increases rhizobial fitness under starvation and in competition for nodules, thus representing a key path for evolutionary conflict in the legume/rhizobia mutualism. Because cellular PHB can supply enough energy to power at least one cellular division, PHB should be included in estimates of rhizobial fitness.