Speciation can involve the evolution of ‘cryptic’ reproductive isolation that occurs after copulation but before hybrid offspring are produced. Because such cryptic barriers to gene exchange involve post-mating sexual interactions, analyses of their evolution have focused on sexual conflict or traditional sexual selection. Here, we show that ecological divergence between populations of herbivorous walking sticks is integral to the evolution of cryptic reproductive isolation. Low female fitness following between-population mating can reduce gene exchange between populations, thus acting as a form of cryptic isolation. Female walking sticks show reduced oviposition rate and lower lifetime fecundity following between-population versus within-population mating, but only for mating between populations using different host-plant species. Our results indicate that even inherently sexual forms of reproductive isolation can evolve as a by-product of ecological divergence and that post-mating sexual interactions do not necessarily evolve independently of the ecological environment.