Planktonic Nostocales cyanobacteria represent a challenge for microbiological research because of the wide range of cyanotoxins that they synthesize and their invasive behavior, which is presumably enhanced by global warming. To gain insight into the phylogeography of potentially toxic Nostocales from Mediterranean Europe, 31 strains of Anabaena (Anabaena crassa, A. lemmermannii, A. mendotae, and A. planctonica), Aphanizomenon (Aphanizomenon gracile, A. ovalisporum), and Cylindrospermopsis raciborskii were isolated from 14 freshwater bodies in Spain and polyphasically analyzed for their phylogeography, cyanotoxin production, and the presence of cyanotoxin biosynthesis genes. The potent cytotoxin cylindrospermopsin (CYN) was produced by all 6 Aphanizomenon ovalisporum strains at high levels (5.7 to 9.1 μg CYN mg(-1) [dry weight]) with low variation between strains (1.5 to 3.9-fold) and a marked extracellular release (19 to 41% dissolved CYN) during exponential growth. Paralytic shellfish poisoning (PSP) neurotoxins (saxitoxin, neosaxitoxin, and decarbamoylsaxitoxin) were detected in 2 Aphanizomenon gracile strains, both containing the sxtA gene. This gene was also amplified in non-PSP toxin-producing Aphanizomenon gracile and Aphanizomenon ovalisporum. Phylogenetic analyses supported the species identification and confirmed the high similarity of Spanish Anabaena and Aphanizomenon strains with other European strains. In contrast, Cylindrospermopsis raciborskii from Spain grouped together with American strains and was clearly separate from the rest of the European strains, raising questions about the current assumptions of the phylogeography and spreading routes of C. raciborskii. The present study confirms that the nostocalean genus Aphanizomenon is a major source of CYN and PSP toxins in Europe and demonstrates the presence of the sxtA gene in CYN-producing Aphanizomenon ovalisporum.