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 coevolve under a phenotype matching rule and how this affects reproductive isolation. We show that the evolution of female preferences increases the mating success of males with 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 (deterministic 'preference cycling' triggered by stochasticity). Thus, counterintuitively, the process of establishing premating isolation proves rather fragile if both male and female mate choice contribute to assortative mating.