Counter-flow heat exchangers constitute a major component of several thermo-mechanical energy storage technologies. They are used to transfer thermal energy between the working fluid and the storage fluid, and exergy losses undergone during this process can affect significantly the efficiency of the whole system. The principal sources of loss are irreversible heat transfer and pressure losses, and optimisation is required to find the right balance between them. In this article we focus on the effect that the variation of the specific heat capacity of some fluids has on the thermal component of the loss. First, we assume a linear dependence of the heat capacity with temperature and study the problem analytically, showing that a minimum exergetic loss exists when the variation is different for the two fluids. The effect is negligible in low-performance heat exchangers but it is found to have a critical impact in high-performance devices with a very high number of transfer units. Second, the minimum loss for several couples of real fluids is computed numerically and compared with the prediction of the analytical model. Finally, the effect that this phenomenon has on the optimisation of a flat-plate, counter-flow heat exchanger is studied.