Cryptosporidium, a zoonotic pathogen, is able to infect a wide range of hosts including wild and domestic animals, and humans. Although it is well known that some parasites are both fish pathogens and recognized agents of zoonosis with a public health impact, little information is available concerning the prevalence of Cryptosporidium in wild aquatic environments. To evaluate the prevalence of Cryptosporidium spp. in commercially important edible marine fish in different European seas (English channel, North sea, Bay of Biscay, Celtic sea and Mediterranean sea), 1,853 specimens were collected as part of two surveys. Nested PCR followed by sequence analysis at the 18S rRNA gene locus was used to identify Cryptosporidium spp. The overall prevalence of Cryptosporidium spp. in sampled fish reached 2.3% (35 out of 1,508) in a first campaign and 3.2% (11 out of 345) in a second campaign. Sequence and phylogenetic analysis of positive samples identified Cryptosporidium parvum (n = 10) and seven genotypes which exhibited between 7.3 and 10.1% genetic distance from C. molnari, with the exception of one genotype which exhibited only 0.5–0.7% genetic distance from C. molnari. Among 31 analyzed fish species, 11 (35.5%) were identified as potential hosts for Cryptosporidium. A higher prevalence of Cryptosporidium spp. was observed in larger fish, in fish collected during the spring-summer period, and in those caught in the North East Atlantic. Pollachius virens (saithe) was the most frequently Cryptosporidium positive species. In fish infected by other parasites, the risk of being Cryptosporidium positive increased 10-fold (OR: 9.95, CI: 2.32–40.01.04, P = 0.0002). Four gp60 subtypes were detected among the C. parvum positive samples: IIaA13G1R1, IIaA15G2R1, IIaA17G2R1, and IIaA18G3R1. These C. parvum subtypes have been previously detected in terrestrial mammals and may constitute an additional source of infection for other animals and in particular for humans. Microscopical examination of histological sections confirmed the presence of round bodies suggestive of the development of C. parvum within digestive glands. We report herein the first epidemiological and molecular data concerning the detection of Cryptosporidium in edible marine fish in European seas surrounding France broadening its host range and uncovering potential novel infection routes.