We describe a new species of egg-eating sea snake, Aipysurus mosaicus sp. nov., from northern Australia and southern New Guinea. This species was previously considered to be an allopatric population of A. eydouxii, which occurs throughout the Sunda Shelf and in New Guinea. Molecular analyses reveal these two species to be sister lineages with fixed nucleotide substitutions at three independent mitochondrial and nuclear loci, and a deep phylogenetic divergence exceeding that of all other sampled species pairs in Aipysurus. Aipysurus mosaicus sp. nov. is also distinguished from A. eydouxii by morphological characters relating to scalation (e.g. number of ventral scales), colour pattern (e.g. number and shape of transverse body bands), internal soft anatomy (e.g. position of heart in relation to ventral scales), and skeletal morphology (e.g. shape of nasal and caudal neural spines). Additional sampling is needed to clarify the extent of geographic contact between A. eydouxii and the new species in New Guinea where they appear to be sympatric. It is likely that the boundaries between these taxa will be mirrored in other coastal sea snakes with ranges spanning the deep waters of the Timor Trench; discovery of such cryptic species will have important implications for conservation of this highly diverse but relatively poorly studied group of marine vertebrates.