Evolutionary theory suggests that polymorphic traits can be maintained within a single population only under specific conditions, such as negative frequency-dependent selection or heterozygote advantage. Non-venomous turtle-headed sea snakes (Emydocephalus annulatus) living in shallow bays near Noumea in New Caledonia exhibit three colour morphs: black, black-and-white banded, and an intermediate (grey-banded) morph that darkens with age. We recorded morph frequencies during 18 consecutive years of surveys, and found that the numbers of recruits (neonates plus immigrants) belonging to each morph increased in years when that morph was unusually rare in the population, and decreased when that morph was unusually common. Thus, morph frequencies are maintained by negative frequency-dependent selection. We interpret the situation as Batesian mimicry of highly venomous sea snakes (Aipysurus, Hydrophis, Laticauda) that occur in the same bays, and range in colour from black-and-white banded to grey-banded. Consistent with the idea that mimicry may protect snakes from attack by large fish and sea eagles, behavioural studies have shown that smaller fish species in these bays flee from banded snakes but attack black individuals. As predicted by theory, mimetic (banded) morphs are less common than the cryptically-coloured melanic morph.