Toxic cyanobacterial blooms pose significant public health and water quality risks in surface waters worldwide.Changes in global climate and rainfall patterns have led to increased frequency of cyanobacterial blooms, rapid shifts in the distributions of many cyanobacteria species and emergence of novel toxin types in previously toxin-free regions. Our study investigated the emergence of anatoxin-a (ATX-a) producing cyanobacteria in Australian surface waters (a continent previously assessed as being anatoxin-free) using microscopy, nested Polymerase Chain Reaction (PCR)-based amplification of the ATX-a synthetase gene and direct detection of ATX-a by Enzyme-Linked Immunosorbent Assay (ELISA). Screening samples were collected over a period of seven years across the state of Victoria, Australia. Here, we (1) detected ATX-a producing cyanobacteria, including Cuspidothrix issatschenkoi, Aphanizomenonaceae, Dolichospermum sp. and Oscillatoria sp., from 31 different sampling locations, (2) identified the presence and distribution of cyanobacteria encoding the anaC gene required for ATX-a production, and (3) determined the presence and concentration of ATX-a in our samples. Our study highlights the importance of regular investigation to monitor emerging and shifting distributions of toxic cyanobacteria worldwide in a period of increased eutrophication and rising surface water temperatures.