Sexual interactions play an important role in the evolution of reproductive isolation, with important consequences for speciation. Theoretical studies have focused on the evolution of mate preferences in each sex separately. However, mounting empirical evidence suggests that premating isolation often involves mutual mate choice. Here, using a population genetic model, we investigate how female and male mate choice co-evolve (phenotype matching rule) and how this affects reproductive isolation. We show that the evolution of female preferences increases the mating success of males showing reciprocal preferences, favouring mutual mate choice. However, the evolution of male preferences weakens indirect selection on female preferences and, with weak genetic drift, the coevolution of female and male mate choice leads to periodic episodes of random mating with increased hybridization rate ('preference cycling'). Thus, counterintuitively, the process of establishing premating isolation proves very fragile if both sexes can contribute to assortative mating.