Habitat loss and fragmentation affect species richness in fragmented habitats and can lead to immediate or time-delayed species extinctions. Asynchronies in extinction and extinction debt between interacting species may have severe effects on ecological networks. However, these effects remain largely unknown. We evaluated the effects of habitat patch and landscape changes on antagonistic butterfly larvae-plant trophic networks in Mediterranean grasslands in which previous studies had shown the existence of extinction debt in plants but not in butterflies. We sampled current species richness of habitat-specialist and generalist butterflies and vascular plants in 26 grasslands. We assessed the direct effects of historical and current patch and landscape characteristics on species richness and on butterfly larvae-plant trophic network metrics and robustness. Although positive species- and interactions-area relationships were found in all networks, structure and robustness was only affected by patch and landscape changes in networks involving the subset of butterfly specialists. Larger patches had more species (butterflies and host plants) and interactions but also more compartments, which decreased network connectance but increased network stability. Moreover, most likely due to the rescue effect, patch connectivity increased host-plant species (but not butterfly) richness and total links, and network robustness in specialist networks. On the other hand, patch area loss decreased robustness in specialist butterfly larvae-plant networks and made them more prone to collapse against host plant extinctions. Finally, in all butterfly larvae-plant networks we also detected a past patch and landscape effect on network asymmetry, which indicates that there were different extinction rates and extinction debts for butterflies and host plants. We conclude that asynchronies in extinction and extinction debt in butterfly-plant networks provoked by patch and landscape changes caused changes in species richness and network links in all networks, as well as changes in network structure and robustness in specialist networks.