The recent interest in multi-functional agricultural landscapes has not been matched with formal assessment of the roles that trees play across the spectrum of ecosystem services (ESs) provided in Sub-Saharan Africa (SSA). A structured literature review (1995–2014) assessed 350 journal articles about provision of one or more ESs by trees on farms and in agricultural landscapes in SSA. This revealed information on 15 ESs from studies in 23 countries covering arid (1% of studies), semi-arid (49%), sub-humid (26%) and humid (24%) agro-ecological zones. The majority of the studies reported provisioning (39%) and supporting (35%) followed by regulating (26%) ESs while studies on cultural services were scarce. Beneficial impacts of trees were dominating (58%), in particular in semi-arid zones where they were associated with enhancing water and nutrient cycling. A decline in some ESs was reported in 15% of the studies, while 28% found no effect of trees. Although the effects of trees were mainly positive, a decline in crop production was noted as a key trade-off against the provisions of ESs, such as modification of microclimate. This highlights the need to manage trade-offs among impacts of trees on ES provision to reduce competition and increase complementarity between trees and crops.