In the last 25 years, nematode parasites of the genus Anisakis have attracted international attention from various socio-economic sectors, with serious concern about the impact of these parasites on seafood quality and safety, and public health (related to both zoonoses and allergy). A knowledge-based understanding of the population structure of Anisakis spp. is useful to provide valuable data about the infection dynamics, host specificity and its ability to adapt to local environments and to climate change by adapting to the food-web structure. This study first aimed to investigate the taxonomic biodiversity of Anisakis spp. collected from commercial fish and cetacean species from the most significant Northeast Atlantic fishing grounds and evaluate the ecological connections of A. simplex and A. pegreffii (L3 and adults) in cetaceans and fish from NW Spain, through the analysis of their genetic diversity and population structure. A total of 1399 Anisakis spp. L3 larvae from six fish species and 475 adults from six cetacean species were identified using the ITS rDNA region as a molecular marker. Molecular identification allowed for the first detection of A. berlandi in European waters parasitizing the long-finned pilot whales Globicephala melas and the first report of A. nascettii and A. zhiphidarum infecting the striped dolphin Stenella coeruleoalba, as well as the identification of A. simplex, A. pegreffii and the hybrid genotype between both species. The analysis of the mitochondrial cytochrome oxidase 2 gene of A. simplex and A. pegreffii, the most prevalent species in FAO area 27, revealed panmictic populations for both species with high haplotype diversity. The predatory–prey relationship involving two major fish species (European hake and blue whiting) and the common dolphin appears to provide an important mechanism for maintaining genetic diversity and structure in major Anisakis species in the NE Atlantic.