Habitat loss and associated fragmentation are major drivers of biodiversity decline, and understanding how they affect population processes (e.g. dispersal) is an important conservation goal. In a large-scale test employing 10 × 10 km units of replication, three species of Australian birds, the fuscous honeyeater, yellow-tufted honeyeater and white-plumed honeyeater, responded differently to fragmentation. The fuscous and yellow-tufted honeyeaters are 'decliners' that disappeared from suitable habitat in landscapes where levels of tree-cover fell below critical thresholds of 17 and 8%, respectively. The white-plumed honeyeater is a 'tolerant' species whose likelihood of occurrence in suitable habitat was independent of landscape-level tree-cover. To determine whether the absence of the two decliner species in low tree-cover landscapes can be explained by reduced genetic connectivity, we looked for signatures of reduced mobility and gene flow in response to fragmentation across agricultural landscapes in the Box-Ironbark region of north-central Victoria, Australia. We compared patterns of genetic diversity and population structure at the regional scale and across twelve 100 km(2) landscapes with different tree-cover extents. We used genetic data to test landscape models predicting reduced dispersal through the agricultural matrix. We tested for evidence of sex-biased dispersal and sex-specific responses to fragmentation. Reduced connectivity may have contributed to the disappearance of the yellow-tufted honey-eater from low tree-cover landscapes, as evidenced by male bias and increased relatedness among males in low tree-cover landscapes and signals of reduced gene flow and mobility through the agricultural matrix. We found no evidence for negative effects of fragmentation on gene flow in the other decliner, the fuscous honeyeater, suggesting that undetected pressures act on this species. As expected, there was no evidence for decreased movement through fragmented landscapes for the tolerant white-plumed honeyeater. We demonstrated effects of habitat loss and fragmentation (stronger patterns of genetic differentiation, increased relatedness among males) on the yellow-tufted honeyeater above the threshold at which probability of occurrence dropped. Increasing extent and structural connectivity of habitat should be an appropriate management action for this species and other relatively sedentary woodland specialist species for which it can be taken as representative.