Phosphorus (P) availability to crops may be affected by agronomic measures either through the modification of soil properties or through crop impact on soil P dynamics. Most legumes display one or more of the various adaptive strategies that enhance Nitrogen (N) and P acquisition and use and some may represent a sustainable solution to improve inputs and cycling of these two most limiting nutrients in cropping systems. We assessed some selected legumes for their ability to mobilize P alongside their rhizospheric characteristics in soils of contrasting levels of soil fertility degradation through pot and field experiments. Some 18 varieties of 7 legume species that portray different mechanisms of P uptake in P limiting conditions were compared with the P responders in a pot experiment to screen and select those that have potential to enhance P availability in the maize based cropping systems of western Kenya. Three selected P efficient species, pigeon pea (ICPL 87091), white lupine (Kiev mutant) groundnut (Uganda red) and two P responders, soybean (TGX 1448) and Lablab (Rongai), denoted CC, WL, GN, SB and LB respectively in the text and Maize (MZ) were then grown in the field to assess their growth and P mobilization in four sites that differed in their level of soil fertility degradation. They were also grown in pots using soils sampled from a highly degraded (BKG), a fairly degraded (KER) and a fertile site, (KON) and three fertilizer treatments, Triple Super Phosphate (TSP), Minjingu Rock Phosphate (MRP) and no phosphorus (NoP). There was no site effect on plant growth as measured on dry matter production for most legumes. However, legume grain yield production was significantly low for one site (25-113 kg/ha for SB and CC respectively) compared to the highest yielding site (92 – 2536 kg/ha) while maize yield differed significantly across the sites with increasing soil fertility. P accumulation in the P- efficient legumes (CC, GN and WL) did not respond to P application. In the pot experiment, P efficient species performed better in medium fertility soil while P responders showed higher performance in high fertility soil. Response to P across soil degradation levels in pots showed that source of P did not affect the P efficient species CC, GN and WL. LB and SB responded to TSP while MZ responded to both TSP and MRP (p < 0.0001). There was no site effect on percentage root mycorrhizal colonization which was lowest in WL (36) and CC (42.3) followed by a significantly higher colonization in LB (50.7) and SB (55.2) and highest in GN (68.4) and MZ (69.4). Rhizosphere acid phosphatase activity was significantly higher in WL (p < 0.0001) than in GN and MZ that did not differ from one another. These results point to a promising potential in introducing legumes to the low P cropping systems of western Kenya.