The world is challenged to meet the food demand of a growing population, especially in developing countries. Given the ambitious plans to scale up agroforestry in Africa, an improved understanding of the effect of agroforestry practices on the already challenged food security of rural households is crucial. The present study was undertaken to assess how on-farm trees impacted food security in addition to other household income sources in Rwanda. In each of the six agroecologies of Rwanda, a stratified sampling procedure was used where two administrative cells (4th formal administrative level) were selected in which households were randomly selected for interviews. A survey including 399 farmers was conducted and farmers were grouped in three types of agroforestry practice (i) low practitioners (LAP) represented by the first tertile, (ii) medium practitioners (MAP) represented by the second tertile and (iii) high practitioners (HAP) represented by the third tertile of households in terms of tree number. Asset values, household income sources, crop production, farm size, crop yield, and food security (food energy needs) were quantified among the types of agroforestry practice. A larger proportion of HAP households had access to adequate quantity and diversity of food when compared with MAP and LAP households. Food security probability was higher for households with more resources, including land, trees and livestock, coinciding with an increased crop and livestock income. We found no difference in asset endowment among types of agroforestry practices, while farmers in agroecologies with smaller farms (0.42 ha to 0.66 ha) had more on-farm trees (212 to 358 trees per household) than farms in agroecologies with larger farms (0.96 ha to 1.23 ha) which had 49 to 129 trees per household, probably due to differences in biophysical conditions. A positive association between tree density and food security was found in two out of six agroecologies. The proportion of income that came from tree products was high (> 20%) for a small fraction of farmers (12%), with the more food insecure households relying more on income from tree products than households with better food security status. Thus, tree income can be percieved as a “safety net” for the poorest households.