Parallel evolution of similar traits in independent populations that inhabit ecologically similar environments strongly implicates natural selection as the cause of evolution. Parallel speciation is a special form of parallel evolution where traits that determine reproductive isolation evolve repeatedly, in closely related populations, as by-products of adaptation to ecological conditions. The outcome of such parallel evolution is that ecologically divergent pairs of populations exhibit greater levels of reproductive isolation than ecologically similar pairs of populations of a similar or younger age. The parallel evolution of reproductive isolation provides strong evidence for natural selection in the process of speciation, but only one conclusive example from nature is known. Populations of the walking-stick insect Timema cristinae that use different host-plant species have diverged in body size and shape, host preference, behaviour and the relative frequency of two highly cryptic colour-pattern morphs. Here we report that divergent selection for host adaptation, and not genetic drift, has promoted the parallel evolution of sexual isolation in this species. Our findings represent a clear demonstration that host-plant adaptation can play a crucial and repeatable role in the early stages of speciation.