The gray whale Eschrichtius robustus, the only living member of the eschrichtiid lineage, currently inhabits only the North Pacific. Interestingly, however, the holotypes of both E. robustus and the late Miocene Archaeschrichtius ruggieroi (the oldest known eschrichtiid species) come from the North Atlantic and the Mediterranean, respectively. Here we describe a partial mysticete mandible from the Pliocene (3.71–2.76 Ma) of Belgium (Eastern North Atlantic). This new fossil displays a combination of morphological features that makes it nearly identical to modern E. robustus. Nevertheless, given its incomplete nature, the studied specimen is here identified in open nomenclature as belonging to Eschrichtius sp. The recognition of such an early record of Eschrichtius in the North Atlantic suggests that this genus developed a circum-Northern Hemisphere distribution not later than in Pliocene times, thus complicating our understanding of its origin, evolutionary history, and palaeobiogeographic patterns.