Global warming is causing ice retreat in glaciers worldwide, most visibly over the last few decades in some areas of the planet. One of the most affected areas is the region of Tierra del Fuego (southern South America). Vascular plant recolonisation of recently deglaciated areas in this region is initiated by Gunnera magellanica, which forms symbiotic associations with the cyanobacterial genus Nostoc, a trait that likely confers advantages in this colonisation process. This symbiotic association in the genus Gunnera is notable as it represents the only known symbiotic relationship between angiosperms and cyanobacteria. The aim of this work was to study the genetic diversity of the Nostoc symbionts in Gunnera at three different, nested scale levels: specimen, population and region. Three different genomic regions were examined in the study: a fragment of the small subunit ribosomal RNA gene (16S), the RuBisCO large subunit gene coupled with its promoter sequence and a chaperon-like protein (rbcLX) and the ribosomal internal transcribed spacer (ITS) region. The identity of Nostoc as the symbiont was confirmed in all the infected rhizome tissue analysed. Strains isolated in the present study were closely related to strains known to form symbioses with other organisms, such as lichen-forming fungi or bryophytes. We found 12 unique haplotypes in the 16S rRNA (small subunit) region analysis, 19 unique haplotypes in the ITS region analysis and 57 in the RuBisCO proteins region (rbcLX). No genetic variability was found among Nostoc symbionts within a single host plant while Nostoc populations among different host plants within a given sampling site revealed major differences. Noteworthy, interpopulation variation was also shown between recently deglaciated soils and more ancient ones, between eastern and western sites and between northern and southern slopes of Cordillera Darwin. The cell structure of the symbiotic relationship was observed with low-temperature scanning electron microscopy, showing changes in morphology of both cyanobiont cells (differentiate more heterocysts) and plant cells (increased size). Developmental stages of the symbiosis, including cell walls and membranes and EPS matrix states, were also observed.