While the effects of deforestation and habitat fragmentation on parasite prevalence or richness are well investigated, host-parasite networks are still understudied despite their importance in understanding the mechanisms of these major disturbances. Because fragmentation may negatively impact species occupancy, abundance and co-occurrence, we predict a link between spatiotemporal changes in habitat and the architecture of host-parasite networks. For this, we used an extensive data set on 16 rodent species and 29 helminth species from seven localities of South-East Asia. We analysed the effects of rapid deforestation on connectance and modularity of helminth-parasite networks. We estimated both the degree of fragmentation and the rate of deforestation through the development of land uses and their changes through the last 20 to 30 years in order to take into account the dynamics of habitat fragmentation in our statistical analyses. We found that rapid fragmentation does not affect helminth species richness per se but impacts host-parasite interactions as the rodent-helminth network becomes less connected and more modular. Our results suggest that parasite sharing among host species may become more difficult to maintain with the increase of habitat disturbance.