Pro-social punishment, whereby cooperators punish defectors, is often suggested as a mechanism that maintains cooperation in large human groups. Importantly, models that support this idea have to date only allowed defectors to be the target of punishment. However, recent empirical work has demonstrated the existence of anti-social punishment in public goods games. That is, individuals that defect have been found to also punish cooperators. Some recent theoretical studies have found that such anti-social punishment can prevent the evolution of pro-social punishment and cooperation. However, the evolution of anti-social punishment in group-structured populations has not been formally addressed. Previous work has informally argued that group-structure must favour pro-social punishment. Here we formally investigate how two demographic factors, group size and dispersal frequency, affect selection pressures on pro- and anti-social punishment. Contrary to the suggestions of previous work, we find that anti-social punishment can prevent the evolution of pro-social punishment and cooperation under a range of group structures. Given that anti-social punishment has now been found in all studied extant human cultures, the claims of previous models showing the co-evolution of pro-social punishment and cooperation in group-structured populations should be re-evaluated.