Nodule bacteria or rhizobia are soil microorganisms that form a symbiotic relationship with legumes. Symbiotic cooperation results in the development of root nodules on legumes that contain nitrogen-fixing rhizobia producing nitrogen compounds used by plants for growth. The nitrogen fixed by nodule bacteria symbiotically in the form of organic and inorganic compounds can be released by legumes into the rhizosphere increasing soil fertility. Inoculation of legumes with effective rhizobial strains is an important way to improve plant growth and productivity without significant cost. Thereby the isolation of nodule bacteria with the best symbiotic properties is of great interest. Black locust (Robinia pseudoacacia L.) is a fast growing and drought resistant leguminous tree that can grow in poor soils. Black locust is considered as tree species that has economic and ecological importance. The leguminous plant can be used for biomass production for bioenergy, in land reclamation improving soil quality, etc. The aim of this work was to study the symbiotic properties of the rhizobia isolated from black locust root nodules as well as to evaluate the effect of the nodule bacteria on leguminous tree biomass production. Five isolates of nodule bacteria were obtained from the root nodules of black locust growing in different areas of Europe (Mlyňany Arboretum, Slovakia and Kyiv, Ukraine). The isolated rhizobia were tested for their ability to form an effective nitrogen-fixing symbiosis with black locust. Nodule number and weight, nodule nitrogen fixing activity and shoot weight were estimated after 60 days of black locust growth. All the rhizobia where grown on YEM solid medium. They formed circular, opaque, white, raised or convex, mucoid colonies about 2–3 mm in diameter. The tested microorganisms showed variation in their nodulation activity. A large number of nodules were observed on black locust roots inoculated with two rhizobial isolates found in the nodules of black locust grown in Ukraine. Symbiotic bacteria isolated from the nodules of black locust in Slovakia were shown to form low nodule counts. The nitrogen fixing activity of root nodules induced by the rhizobia occupying black locust nodules in Slovakia was lower than those induced by bacterial isolates from Ukraine. Inoculation of black locust seeds with some rhizobial isolates significantly improved biomass production of above mentioned leguminous tree. The results of our experiments indicate the need for further study of effective black locust nodule bacteria to evaluate their potential for application as biofertilizers.