We describe two new species of Varanus, one each endemic to the Louisiade and Tanimbar Archipelagos in Papua New Guinea and Indonesia, respectively. The new species belong to the subgenus Euprepiosaurus and, therein, to the widely distributed and relatively species-rich Varanus indicus group. They can be distinguished from all other recognised species by scalation, colour-pattern and genetic differences. The new species from Tanimbar is most closely related to V. indicus and V. melinus, from which it can be distinguished by its dark blue/grey tongue and higher middorsal and midventral scale counts. The new species from the Louisiades can be distinguished from its phylogenetically and geographically nearest relative, V. chlorostigma, by the presence of dorsal crossbands, the mostly pink tongue mottled with grey, and higher midbody scale count. The Louisiades constitute the easternmost archipelago of Milne Bay Province in eastern Papua New Guinea, and they host a diverse herpetofauna with a high degree of endemism; Varanus louisiadensis sp. nov. increases the known number of herpetofaunal endemics in that archipelago to 60. The Tanimbar Islands are situated in the southern part of Maluku Province (Moluccas), Indonesia, and are a minor centre of vertebrate endemism; Varanus tanimbar sp. nov. increases the number of known herpetofaunal endemics there to six.