Monitor lizards (genus Varanus) inhabited Europe at least from the early Miocene to the Pleistocene. Their fossil record is limited to about 40 localities that have provided mostly isolated vertebrae. Due to the poor diagnostic value of these fossils, it was recently claimed that all the European species described prior to the 21st century are not taxonomically valid and a new species, Varanus amnhophilis, was erected on the basis of fragmentary material including cranial elements, from the late Miocene of Samos (Greece). We re-examined the type material of Varanus marathonensis Weithofer, 1888, based on material from the late Miocene of Pikermi (Greece), and concluded that it is a valid, diagnosable species. Previously unpublished Iberian material from the Aragonian (middle Miocene) of Abocador de Can Mata (Vallès-Penedès Basin, Barcelona) and the Vallesian (late Miocene) of Batallones (Madrid Basin) is clearly referable to the same species on a morphological basis, further enabling to provide an emended diagnosis for this species. Varanus amnhophilis appears to be a junior subjective synonym of V. marathonensis. On the basis of the most complete fossil Varanus skeleton ever described, it has been possible to further resolve the internal phylogeny of this genus by cladistically analyzing 80 taxa coded for 495 morphological and 5729 molecular characters. Varanus marathonensis was a large-sized species distributed at relatively low latitudes in both southwestern and southeastern Europe from at least MN7+8 to MN12. Our cladistic analysis nests V. marathonensis into an eastern clade of Varanus instead of the African clade comprising Varanus griseus, to which it had been related in the past. At least two different Varanus lineages were present in Europe during the Neogene, represented by Varanus mokrensis (early Miocene) and V. marathonensis (middle to late Miocene), respectively.