Theory of local adaptation predicts that nonadapted migrants will suffer increased costs compared to local residents. Ultimately this process can result in the reduction of gene flow and culminate in speciation. Here, we experimentally investigated the relative fitness of migrants in foreign habitats, focusing on diverging lake and river ecotypes of three-spined sticklebacks. A reciprocal transplant experiment performed in the field revealed asymmetric costs of migration: whereas mortality of river fish was increased under lake conditions, lake migrants suffered from reduced growth relative to river residents. Selection against migrants thus involved different traits in each habitat but generally contributed to bidirectional reduction in gene flow. Focusing particularly on the parasitic environments, migrant fish differed from resident fish in the parasite community they harboured. This pattern correlated with both cellular phenotypes of innate immunity as well as with allelic variation at the genes of the major histocompatibility complex. In addition to showing the costs of migration in three-spined sticklebacks, this study highlights the role of asymmetric selection particularly from parasitism in genotype sorting and in the emergence of local adaptation.