A study was conducted in three different soils (Toje, Hatso and Alajo) to evaluate the effectiveness of the indigenous rhizobia that nodulate five indigenous /or introduced tree legumes (Albizia lebbeck, Acacia mangium, Acacia auriculiformis, Mellitia thonningii and Leucaena leucocephala,) as well as their ability to nodulate other legumes (Cajanus cajan, Crotalaria ochroleuca and Vigna unguiculata) other than their host legumes. The results indicate that, indigenous rhizobia capable of nodulating each of the five tree legumes were present in all the three soils used for the study with the native rhizobia population ranging from 22 cells /g soil in Alajo soil to 5200 cells /g soil in either Hatso or Toje series. Rhizobia isolates from Mellitia thonningii were specific as they nodulated only their host legumes whilst that from Leucaena leucocephala, Crotalaria ochroleuca and Cajanus cajan were moderately promiscuous, with NGR 234 being highly promiscuous. Over 63% of the 200 rhizobia isolates were found to be ineffective on the five legume trees tested, whilst almost 18% were either found to be moderately effective or effective. The majority of the isolates from the five tree legumes were found to be ineffective on their respective host plant with ineffectiveness ranging from almost 43% in the case of Acacia auriculiformis to 88% in the case of Acacia mangium isolates. The high proportion of ineffective isolates (63%) and relatively low proportion of effective (18%) or moderately effective (18%) isolates call for the need for inoculation of the tree legumes in this study with an effective and competitive strains for maximum nodulation and nitrogen fixation.