An instruction decoder (14) is responsive to a conditional compare instruction to generate control signals for controlling processing circuitry (4) to perform a conditional compare operation. The conditional compare operation comprises: (i) if a current condition state of the processing circuitry (4) passes a test condition, then performing a compare operation on a first operand and a second operand and setting the current condition state to a result condition state generated during the compare operation; and (ii) if the current condition state fails the test condition, then setting the current condition state to a fail condition state specified by the conditional compare instruction. The conditional compare instruction can be used to represent chained sequences of comparison operations where each individual comparison operation may test a different kind of relation between a pair of operands.