Killer whales (Orcinus orca) have group-specific call repertoires that can be used to track groups and populations using passive acoustic monitoring. To provide a detailed description of the Icelandic killer whale repertoire and its variation, we analyzed acoustic data collected in five locations between 1985 and 2016. Calls were classified manually, and CART and random forest analyses were employed to validate the manual classification. A total of 91 call categories (including call types and subtypes) were defined. Most call categories were recorded in more than one location, with the highest proportion shared between herring grounds in Vestmannaeyjar (South) and Breiðafjörður (West). However, both locations included call categories that were not recorded elsewhere in Iceland. Recordings from past herring wintering grounds in eastern Iceland included few call categories that matched other locations. Sample sizes from Reykjanes (Southwest) and Skjálfandi (North) were small and did not include unique call categories. The relative occurrence of call categories in Vestmannaeyjar changed little over a 14-year period (2002–2016), although shorter-term changes between years were observed that appeared to correlate to changes in individuals identified. This comparison of acoustic repertoires provides valuable information on the social structure and movement patterns of herring-eating killer whales around Iceland.