The land cover and structure of agricultural landscapes may influence the abundance and diversity of natural enemies of crop pests. However, these landscapes are continuously evolving due to changing land uses and agricultural practices. Here we assess changes in land use and landscape structure in a landscape in the Rift Valley region of Ethiopia, and explore the impact these changes are likely to have on the capacity of the landscape to support communities of natural enemies of maize stemborers Busseola fusca (Fuller). Land use and landscape structure were assessed in three periods over the last 30 years using focus group discussions with farmers and land use analysis through remote sensing. Natural enemies were sampled in maize fields adjacent to simple hedgerows, complex hedgerows, enset fields and khat fields at 1, 10 and 30 m using pitfalls and yellow pan traps in 2014 and 2015. The landscape analysis indicated that landscapes in the study area changed from maize dominated to more diverse small-scale and fragmented agroecosystems with a higher proportion of perennial crops. Maize fields adjacent to enset and complex hedgerows hosted significantly more predators (15.1 ± 9.8 and 22.3 ± 5.1 per trap at 1 m from the border, respectively) than maize fields adjacent to khat and simple hedgerows (7.2 ± 1.1 and 7.3 ± 1.7 per trap at 1 m from the border), and the effects of border type decreased with distance from the border. The abundance of parasitoids and parasitic flies were not influenced by border type. Our findings suggest that the changes in land use and landscape structure may have influenced the capacity of the landscape to support populations of natural enemies of stemborers in different ways. On the one hand smaller field sizes have resulted in more field borders that may support relatively high predator densities; on the other hand, the area of khat increased and the area of enset decreased, which may have a negative effect on predator densities. The overall outcome will depend on the interplay of these opposing effects.