Similarity among species in traits related to ecological interactions is frequently associated with common ancestry. Thus, closely related species usually interact with ecologically similar partners, which can be reinforced by diverse co-evolutionary processes. The effect of habitat fragmentation on the phylogenetic signal in interspecific interactions and correspondence between plant and animal phylogenies is, however, unknown. Here, we address to what extent phylogenetic signal and co-phylogenetic congruence of plant-animal interactions depend on habitat size and isolation by analysing the phylogenetic structure of 12 pollination webs from isolated Pampean hills. Phylogenetic signal in interspecific interactions differed among webs, being stronger for flower-visiting insects than plants. Phylogenetic signal and overall co-phylogenetic congruence increased independently with hill size and isolation. We propose that habitat fragmentation would erode the phylogenetic structure of interaction webs. A decrease in phylogenetic signal and co-phylogenetic correspondence in plant-pollinator interactions could be associated with less reliable mutualism and erratic co-evolutionary change. Copyright ; This study was funded in part by the National Institute of Agricultural Technology (INTA), Balcarce (PNECO1302), the Argentina National Research Council for Research (CONICET) (PIP 01623), the National Fund for Research (PICT 01300), the National University of Comahue (B152/04) and the European Research Council (through an Advanced Grant to JB). M.A.A., G.G. and M.S. are career researchers of CONICET. ; Peer Reviewed