This study identified the carbon sequestration potential of the most valued trees species by farmers in Mayuge district, Uganda. Composite soil samples were collected 1.5 to 2 m away from the tree trunk for carbon content and bulk density at two different soil depths (0-15 cm and 15-30 cm). Soil samples were collected from eight trees of each species, 8-10 years old, on a lixic ferralsol within a radius of 5 km, occurring in different land-use types including land which had been under fallow for 8-10 years. Soil carbon stock did not significantly vary between the different trees and averaged 31.54 Mg ha-1 and 27.05 Mg ha-1 for 0-15 cm and 15-30 cm soil depth, respectively. The effect of land-use and depth on soil carbon stock varied with tree species (p<0.05). Implications of these findings to future studies in Agroforestry as well as to communities in the Lake Victoria rural landscapes are discussed in this paper.