Genetic variation in tolerance for seaweed chemical defenses among populations of marine herbivores is poorly described, either because few marine studies have addressed the issue or because the feeding preferences of populations of marine herbivores rarely differentiate. We address this using the polyphagous amphipod Ampithoe longimana (Crustacea), which commonly consumes, and lives on, terpene-rich brown seaweeds in the tropical genus Dictyota. Previous work demonstrated that in areas where the amphipod and seaweeds overlap geographically, these chemically deterrent seaweeds provide the amphipod with spatial refuges from predation by omnivorous fishes that avoid consuming Dictyota. However, the amphipod's distribution extends northward of the seaweed's distribution, making this benefit of association unavailable to more northerly populations of amphipods. On average, populations sympatric with Dictyota have stronger feeding preference for Dictyota species and greater fitness when raised on Dictyota than do populations that are outside Dictyota's geographic endpoint. These results are consistent with the hypothesis that in areas where the amphipods co-exist with Dictyota, selection favors amphipods that tolerate Dictyota's chemical defenses and thereby access its enemy-free space. Amphipods allopatric with Dictyota are unable to tolerate Dictyota's chemical defenses, either because of selection, drift, or some mix of both forces. A trade-off between preference for Dictyota and for the chemically distinct seaweed Hypnea musciformis is suggested by the finding that populations with high preference for Dictyota tended to have lower preference for Hypnea. However, this population-level pattern appears to be the result of independent evolution and not a genetic trade-off: an analysis of full-sib families within a single population detected heritable variation in preferences for Dictyota and suggested this for Hypnea (although the latter was not statistically significant), yet no family-level covariation was detected. Phylogeographic analysis of mitocondrial DNA and nuclear sequences indicates a strong historical break between populations sympatric with Dictyota and populations more than 500 km beyond Dictyota's geographic endpoint. The historical separation of these most northerly populations could have allowed a random accumulation of alleles to effectively degrade tolerance for Dictyota, although selection may also be responsible for the degradation.