The invasion of a novel habitat often results in a variety of new selective pressures on an individual. One pressure that can severely impact population establishment is predation. The strategies that animals use to minimize predation, especially the extent to which those strategies are habitat or predator specific, will subsequently affect an individuals’ dispersal ability. The invasion of land by a fish, the Pacific leaping blenny, Alticus arnoldorum, offers a unique opportunity to study natural selection following the colonization of a novel habitat. Various studies have examined adaptations in respiration and locomotion, but how these fish have responded to the predation regime on land was unknown. We studied five replicate populations of this fish around the island of Guam and found their body coloration converged on the terrestrial rocky backgrounds on which the fish were most often found. Subsequent experiments confirmed that this background matching significantly reduced predation. Natural selection has therefore selected for background matching in the body coloration of the Pacific leaping blenny to minimize predation, but it is a strategy that is habitat specific. A subsequent comparative study of closely related blenny species suggested that the evolutionary ancestor of the Pacific leaping blenny might have resembled the rocky backgrounds on land prior to invasion. The ancestors of the Pacific leaping blenny may therefore have already been ideally suited for the predator regime on land. More generally our results imply that animals must either already possess antipredator strategies that will be effective in new environments, or must adapt very quickly to new predation pressures if successful establishment is to occur.