Non-social factors can influence animal social structure. In killer whales (Orcinus orca), fish- versus mammal-eating ecological differences are regarded as key ecological drivers of their multilevel society, including group size, but the potential importance of specific target prey remains unclear. Here, we investigate the social structure of herring-eating killer whales in Iceland and compare it to the described social structures of primarily salmon- and seal-eating populations in the Northeast Pacific, which form stable coherent basic units nested within a hierarchical multilevel society. Using 29023 photographs collected over 6 years, we examined the association patterns of 198 individuals combining clustering, social network structure, and temporal patterns of association analysis. The Icelandic population had largely weak but non-random associations, which were not completely assorted by known ranging patterns. A fission–fusion dynamic of constant and temporary associations was observed but this was not due to permanent units joining. The population-level society was significantly structured but not in a clear hierarchical tier system. Social clusters were highly diverse in complexity and there were indications of subsclusters. There was no indication of dispersal nor strong sex differences in associations. These results indicate that the Icelandic herring-eating killer whale population has a multilevel social structure without clear hierarchical tiers or nested coherent social units, different from other populations of killer whales. We suggest that local ecological context, such as the characteristics of the specific target prey (e.g., predictability, biomass, and density) and subsequent foraging strategies may strongly influence killer whale social association patterns.