Human fishing activities are negatively altering marine ecosystems in many ways [1, 2], but scavenging animals such as seabirds are taking advantage of such activities by exploiting fishery discards [3-5]. Despite the well-known impact of fisheries on seabird population dynamics [6-10], little is known about how discard availability affects seabird movement patterns. Using scenarios with and without trawling activity, we present evidence that fisheries modify the natural way in which two Mediterranean seabirds explore the seascape to look for resources during the breeding season. Based on satellite tracking data and a mathematical framework to quantify anomalous diffusion phenomena, we show how the interplay between traveling distances and pause periods contributes to the spatial spreading of the seabirds at regional scales (i.e., 10-250 km). When trawlers operate, seabirds show exponentially distributed traveling distances and a strong site fidelity to certain foraging areas, the whole foraging process being subdiffusive. In the absence of trawling activity, the site fidelity increases, but the whole movement pattern appears dominated by rare but very large traveling distances, making foraging a superdiffusive process. Our results demonstrate human involvement on landscape-level behavioral ecology and provide a new ecosystemic approach in the study of fishery-seabird interactions.