Cyanobacterial blooms are becoming increasingly prevalent worldwide. Sparse historic phytoplankton records often result in uncertainty as to whether bloom-forming species have always been present and are proliferating in response to eutrophication or climate change, or if there has been a succession of new arrivals through recent history. This study evaluated the relative efficacies of germination experiments and automated rRNA intergenic spacer analysis (ARISA) assays in identifying cyanobacteria in a sediment core and thus reconstructing the historical composition of cyanobacterial communities. A core (360 mm in depth) was taken in the central, undisturbed basin of Lake Okaro, New Zealand, a lake with a rapid advance of eutrophication and increasing cyanobacteria populations. The core incorporated a tephra from an 1886 volcanic eruption that served to delineate recent sediment deposition. ARISA and germination experiments successfully detected akinete-forming nostocaleans in sediment dating 120 bp and showed little change in Nostocales species structure over this time scale. Species that had not previously been documented in the lake were identified including Aphanizomenon issatschenkoi, a potent anatoxin-a producer. The historic composition of Chrococcales and Oscillatoriales was more difficult to reconstruct, potentially due to the relatively rapid degradation of vegetative cells within sediment.