Passwords should (and usually are) stored as hashes which means you can very quickly hash the user's entry and compare if it is exactly the same as the password, but by design can't infer any other details about the password if the entry is wrong.
Anything that allows you to compare how 'close' an entry is to the users current password is obviously makes guessing that password far easier.
If your passwords are securely salted and hashed then storing additional old entries shouldn't lower security, and as you say ensures that the user can't reuse a password precisely, but any minor change to the password with result in a completely unrelated hash.