We obtain an exact analytic expression for the average distribution, in the thermodynamic limit, of overlaps between two copies of the same random energy model (REM) at different temperatures. We quantify the non-self averaging effects and provide an exact approach to the computation of the fluctuations in the distribution of overlaps in the thermodynamic limit. We show that the overlap probabilities satisfy recurrence relations that generalise Ghirlanda–Guerra identities to two temperatures. We also analyse the two temperature REM using the replica method. The replica expressions for the overlap probabilities satisfy the same recurrence relations as the exact form. We show how a generalisation of Parisi's replica symmetry breaking ansatz is consistent with our replica expressions. A crucial aspect to this generalisation is that we must allow for fluctuations in the replica block sizes even in the thermodynamic limit. This contrasts with the single temperature case where the extremal condition leads to a fixed block size in the thermodynamic limit. Finally, we analyse the fluctuations of the block sizes in our generalised Parisi ansatz and show that in general they may have a negative variance.