It is well established that soil is a challenging environment for bacteria, where conditions may change rapidly and bacteria have to acclimate and adapt in order to survive. Rhizobia are an important group of soil bacteria due to their ability to establish atmospheric nitrogen-fixing symbioses with many legume species. Some of these legumes are used to feed either humans or cattle and therefore the use of rhizobia can reduce the need for synthetic N-fertilizers. Several environmental factors shape the composition and the activity of rhizobia populations in the rhizosphere. Soil pH and temperature are often considered to be the major abiotic factors in determining the bacterial community diversity. The present review focuses on the current knowledge on the molecular bases of temperature stress response in rhizobia. The effects of temperature stress in the legume-rhizobia symbioses are also addressed.