Soybean is an exotic crop to Ethiopia and may not necessarily have a specific endosymbiont in the soil. However, since it is a promiscuous host, nodulated by cross nodulating rhizobia, it is likely that some compatible endosymbionts exist from heterologous hosts that could nodulate it with effective nitrogen fixation. This necessitated the search for effective indigenous rhizobia isolates and/or compatible and effective cross-inoculating rhizobia that are already adapted to local conditions. To this end, a total of 67 bacterial isolates were trapped from different soil samples using two soybean varieties (Clark-63K and Awassa-95) and one cowpea variety (Bole), to evaluate their diversity and screen for their symbiotic effectiveness. Accordingly, the majority of isolates (93%) were tentatively categorized into alkali producing slow growing Bradyrhiobium spp. and the others (7%) were fast growing and acid producing rhizobia. The isolates showed differences in utilizing various carbon and nitrogen sources and tolerance to acidity, salinity and temperature. The isolates were also diverse in their inherent antibiotic and heavy metal resistance. All the isolates were able to nodulate soybean variety Clark-63K with significant difference in their capacity to infect and effectively fix nitrogen evidenced from variations in nodulation parameters and shoot dry weights. Accordingly, the isolates induced nodulation with nodule number ranging from 2 to 49 nodules plant-1; nodule dry weight of 16 mg plant-1 to 94 mg plant-1 and shoot dry weight between 585 and 1012 mg plant-1. Using shoot dry weight as an indicator of the relative effectiveness of the isolates, 12% of the isolates were highly effective (SE > 80%) and 88% were effective (SE from 50 to 80%) on soybean. Furthermore, the isolates showed narrow and broad host ranges on four legume species viz., cowpea, mung bean, pigeon pea, and peanut. Accordingly, many isolates (67%) formed nodules with effective nitrogen fixation with cowpea (Vigna unguiculata), pigeon pea (Cajanus cajan) (47%), and on few cases with mung bean (Vigna radiata) showing different level of effectiveness. However, the data showed very narrow host range on peanut (Arachis hypogaea) where, only one isolate formed effective nodules.