In an evolutionary context, trusted signals or cues provide individuals with the opportunity to manipulate them to their advantage by deceiving others. The deceived can then respond to the deception by either ignoring the signals or cues or evolving means of deception-detection. If the latter happens, it can result in an arms race between deception and detection. Here, we formally analyse these possibilities in the context of cue-mimicry in prey-predator interactions. We demonstrate that two extrinsic parameters control whether and for how long an arms race continues: the benefits of deception, and the cost of ignoring signals and cues and having an indiscriminate response. As long as the cost of new forms of deception is less than its benefits and the cost of new forms of detection is less than the cost of an indiscriminate response, an arms race results in the perpetual evolution of better forms of detection and deception. When novel forms of deception or detection become too costly to evolve, the population settles on a polymorphic equilibrium involving multiple strategies of deception and honesty, and multiple strategies of detection and trust.