Recent studies have shown that some coral reef fish larvae return to natal reefs, while others disperse to distant reefs. However, the sensory mechanisms used to find settlement sites are poorly understood. One hypothesis is that larvae use olfactory cues to navigate home or find other suitable reef habitats. Here we show a strong association between the clownfish Amphiprion percula and coral reefs surrounding offshore islands in Papua New Guinea. Host anemones and A. percula are particularly abundant in shallow water beneath overhanging rainforest vegetation. A series of experiments were carried out using paired-choice flumes to evaluate the potential role of water-borne olfactory cues in finding islands. Recently settled A. percula exhibited strong preferences for: (i) water from reefs with islands over water from reefs without islands; (ii) water collected near islands over water collected offshore; and (iii) water treated with either anemones or leaves from rainforest vegetation. Laboratory reared-juveniles exhibited the same positive response to anemones and rainforest vegetation, suggesting that olfactory preferences are innate rather than learned. We hypothesize that A. percula use a suite of olfactory stimuli to locate vegetated islands, which may explain the high levels of self-recruitment on island reefs. This previously unrecognized link between coral reefs and island vegetation argues for the integrated management of these pristine tropical habitats.