Possibly yes, unknown in practice, assume that they do.
There are many reasons why a site might store one or more of your old passwords (or, if they have three working brain cells, password hash).
The most common thing is that it will store the last password/hash before the change, in case you come calling and say "that password change wasn't me". In that case they can restore the previous password, which can be preferable over resetting to a new password.
The second common thing is the case you describe - a password policy that states your password can't be equal to the last n passwords you had used. To validate that, those last n passwords or their hashes need to be stored, probably in a seperate database table (so they may or may not be included in a data breach).
Finally, passwords/hashes might be in all kinds of logfiles, debug dumps, backups and other secondary data stores.
As you rarely have insights into the implementation details of websites you use, you will most likely never know. You should therefore assume that they probably do.