Rhizobium leguminosarum is well known for its ability to fix nitrogen (N). In addition, its capacity to solubilize phosphate (Ph) has been receiving attention in recent years. Our ultimate objective was to select a R. leguminosarum bv. viciae isolate with superior Ph-solubilizing ability. The first step was to identify a culture medium that is sensitive and effective in identifying the ability of R. leguminosarum bv. viciae isolates to solubilize Ph. Thirty isolates were evaluated for Ph solubilization in broth and on solid formulations of three media: yeast mannitol extract (YEM), National Botanical Research Institute phosphate nutrient medium (MNBRI), and Pikovskaya phosphate medium (PVK). All media contained 5 g/L CaHPO4 as the only phosphorus (P) source. All 30 isolates increased the Ph concentration in liquid cultures, but the amount of Ph released into solution by individual isolates varied from one medium to another. In contrast, only a subset of the 30 isolates solubilized Ph on the solid cultures. Furthermore, some of the isolates that were able to solubilize Ph were only able to do so on a single medium. Regression analysis revealed no relationship between the Ph concentration in the liquid media and the zones of clearing on the solid media (p > 0.05). Although the pH of all of the liquid media dropped after 12 days of growth of the isolates, a relationship between Ph concentration and pH existed only for the MNBRI medium (r2 = 0.485, p < 0.001). Increasing the amount of N in the MNBRI medium from 0.1 g/L of (NH4)2SO4 to 0.5 g/L of (NH4)2SO4 did not affect the amount of Ph in solution, but it profoundly reduced the survival of the R. leguminosarum by approximately 50-fold. Consequently, the surviving bacteria were either more efficient at solubilizing Ph in the high N media or organic acids released from the lysis of the dead cells solubilized the CaHPO4 source.