Ant supercolonies are the largest cooperative units known in nature. They consist of networks of interconnected nests with hundreds of reproductive queens, where individuals move freely between nests, cooperate across nest boundaries and show little aggression towards non-nestmates. The combination of high queen numbers and free mixing of workers, queens and brood between nests results in extremely low nestmate relatedness. In such low-relatedness societies, cooperative worker behaviour appears maladaptive because it may aid random individuals instead of relatives. Here, we provide a comprehensive picture of genetic substructure in supercolonies of the native wood ant Formica aquilonia using traditional population genetic as well as network analysis methods. Specifically, we test for spatial and temporal variation in genetic structure of different classes of individuals within supercolonies and analyse the role of worker movement in determining supercolony genetic networks. We find that relatedness within supercolonies is low but positive when viewed on a population level, which may be due to limited dispersal of individuals and/or ecological factors such as nest site limitation and competition against conspecifics. Genetic structure of supercolonies varied with both sample class and sampling time point, which indicates that mobility of individuals varies according to both caste and season and suggests that generalizing has to be carried out with caution in studies of supercolonial species. Overall, our analysis provides novel evidence that native wood ant supercolonies exhibit fine-scale genetic substructure, which may explain the maintenance of cooperation in these low-relatedness societies.