Decreasing landscape connectivity, due to habitat loss and agricultural expansion, is a threat for species movement and other flux-dependent ecological processes. Tree cover within the agricultural matrix provides perching sites, dispersal routes, and extra habitat for animals. Isolated trees and living fences in tropical pastures add structural complexity to actual matrices, but their role in landscape connectivity is undervalued. Our main objective was to assess the potential value of small (≤1ha) woody patches for maintaining landscape connectivity in highly fragmented landscapes using birds as focal species. We used high-resolution images and LIDAR data to classify different tree cover types. We assess the probability of connectivity for different hypothetical dispersal distances between woody patches, using a graph-theoretic approach and simulating scenarios that differed in tree cover composition. We estimated the impacts and contribution of tree cover class removals on landscape connectivity. The connectivity index increased widely among scenarios with increasing tree cover composition. The highest connectivity value was obtained in the scenario that included all arboreal elements currently present in the matrix. Small wooded patches and isolated trees contributed from 26% to 59% to overall connectivity. The presence of small (≤1ha) patches of tree cover greatly enhance landscape connectivity for animals with low vagility and behavioral limitations on crossing gaps. Isolated trees and living fences play a crucial role in increasing habitat reachability within rural landscapes and ensuring and enhancing connectivity for animals that perform daily movements at short distances. The spatial distribution of arboreal elements within landscapes could be optimized to increase connectivity and must be considered in conservation planning.