Understanding the degree of connectivity between coastal and island landscapes and nearby coral reefs is vital to the integrated management of terrestrial and marine environments in the tropics. Coral reef fish are capable of navigating appropriate settlement habitats following their pelagic larval phase, but the mechanisms by which they do this are unclear. The importance of olfactory cues in settlement site selection has been demonstrated, and there is increasing evidence that chemical cues from terrestrial sources may be important for some species. Here, we test the olfactory preferences of eight island-associated coral reef fish recruits and one generalist species to discern the capacity for terrestrial cue recognition that may aid in settlement site selection. A series of pairwise choice experiments were used to evaluate the potential role that terrestrial, water-borne olfactory cues play in island-reef recognition. Olfactory stimuli tested included near-shore water, terrestrial rainforest leaf litter, and olfactory cues collected from different reef types (reefs surrounding vegetated islands, and reefs with no islands present). All eight island-associated species demonstrated high levels of olfactory discrimination and responded positively toward olfactory cues indicating the presence of a vegetated island. We hypothesize that although these fish use a suite of cues for settlement site recognition, one mechanism in locating their island/reef habitat is through the olfactory cues produced by vegetated islands. This research highlights the role terrestrial olfactory cues play in large-scale settlement site selection and suggests a high degree of ecosystem connectivity.