Olfaction-based reproductive isolation is widely observed in animals, but little is known about the genetic basis of such isolation mechanisms. Two species of sibling amphibious sea snakes, Laticauda colubrina and L. frontalis live in Vanuatu sympatrically and syntopically, but no natural hybrids have been reported. Adult females of both taxa possess distinctive lipids in the skin, and male L. frontalis distinguishes conspecific females based on olfactory cues. To shed light on the molecular basis of the evolution of olfaction-based isolation mechanisms, olfactory receptor (OR) gene repertoires of both taxa were identified using pyrosequencing-based technology, and orthologous OR gene sets were identified. Few species-specific gene duplications or species-specific gene losses were found. However, the nonsynonymous-to-synonymous substitution rate ratio was relatively higher between orthologous OR genes of L. frontalis and L. colubrina, indicating that L. frontalis and L. colubrina have evolved to possess different olfactory senses. We suggest that L. frontalis and L. colubrina have evolved allopatrically, and this may be a byproduct of the allopatric evolution, and that this dissimilarity may function as a premating isolation barrier, since L. frontalis has returned to the ancestral range (Vanuatu).