Climate change may amplify the adverse effects of fragmentation by also affecting interspecific interactions. Increased competition may reduce the ability of already stressed species to acquire resources (breeding sites and food), reducing recruitment and the long-term viability of species. We assessed how measures of recruitment of native birds were influenced by the area of native vegetation, vegetation characteristics, vegetation change as an indication of degradation, and the occurrence of an increasingly prevalent native competitor (the noisy miner Manorina melanocephala). We recorded avian breeding behavior on 120 forest transects in the box-ironbark forests of south-eastern Australia, in 2010-2011. On the same transects, we measured vegetation characteristics that had previously been measured in 1995-1997 to assess vegetation change during a 13-yr drought. Vegetation area and the abundance of the noisy miner had a greater effect on species' breeding behavior than did local vegetation characteristics and vegetation degradation. Greater abundances of the noisy miner reduced breeding activities of species with a body mass smaller than the noisy miner (<63 g), while breeding increased in some larger (> 63 g) species. Recruitment measures for the noisy miner were positively associated with smaller fragments and greater vegetation change indicating that fragmentation and vegetation degradation have facilitated the colonization or recruitment by the noisy miner. The interaction between climate change, fragmentation and vegetation degradation appears to have led to increased effects of interspecific competition in fragments of native vegetation, with potential adverse effects on the viability of many bird species. The spread and increasing abundance of a hyperaggressive native species suggests that species assemblages will be increasingly disrupted by the interacting effects of climate change, fragmentation, degradation and interspecific interactions.