Extant baleen whales (Cetacea, Mysticeti) are a disparate and species-rich group, but little is known about their fossil record in the northernmost Atlantic Ocean, a region that supports considerable extant cetacean diversity. Iceland's geographical setting, dividing North Atlantic and Arctic waters, renders it ideally situated to shed light on cetacean evolution in this region. However, as a volcanic island, Iceland exhibits very little marine sedimentary exposure, and fossil whales from Iceland older than the late Pleistocene are virtually unknown. Here, we present the first fossil whale found in situ from the Pliocene Tjörnes Formation (c. 4.5 Ma), Iceland's only substantial marine sedimentary outcrop. The specimen is diagnosed as a partial skull from a large right whale (Mysticeti, Balaenidae). This discovery highlights the Tjörnes Formation as a potentially productive fossil vertebrate locality. Additionally, this find indicates that right whales (Eubalaena) and bowhead whales (Balaena) were sympatric, with broadly overlapping latitudinal ranges in the Pliocene, in contrast to the modern latitudinal separation of their living counterparts.