Microscopy, DNA sequencing, and amplified fragment length polymorphism (AFLP) were used to examine variation within Nostoc commune from collections between 72 and 78°S in Victoria Land, Antarctica. Although there is considerable bias of collected material towards southern latitudes, and this material varies greatly in age (collected between 1984 and 2004), an important new phylogeographic pattern was found. DNA sequencing of the tRNAleu(UAA) region, used recently to define form species N. commune, revealed little variation between collections. AFLP analysis, however, split the collected material according to habitat (irrigated soil communities versus ponds), rather than latitude. These results suggest that environmental factors linked to latitude are not the greatest drivers of genetic variation in Victoria Land. These may operate at a lower level but would require intensive sampling within narrowly defined habitat types at a range of latitudes to uncover. We advocate extensive sampling across local environmental gradients based on water availability, comparative culturing, and development of sequence characterised amplified regions (SCARs) across a range of latitudes in future seasons of the Latitudinal Gradient Project.