In theory, natural selection can drive adaptation within species while simultaneously promoting the formation of new species by causing the evolution of reproductive isolation. Cryptic coloration is widespread in nature and is generally considered to be a clear visual example of adaptation. I provide evidence that population divergence in cryptic coloration can also cause reproductive isolation. First, a manipulative field experiment using walking-stick insects demonstrates that the relative survival of different colour-pattern morphs depends on the host-plant species on which they are resting, but only in the presence of avian predation. Second, natural populations adapted to different host plants have diverged in colour-pattern-morph frequencies such that between-host migrants are more likely to be the locally less-cryptic morph than are residents. Collectively, these data indicate that high rates of visual predation on less-cryptic migrants are likely to reduce encounters, and thus interbreeding, between host-associated populations. Comparison with previous estimates of sexual isolation reveals that the contribution of selection against between-host migrants to total premating isolation is as strong as, or stronger than, that of sexual isolation. These findings highlight the potential role of natural selection against migrants between divergent environments in the formation of new species.