You ask people to change their passwords, and when they do so, you store them with the new scheme. You can do that by e.g. requiring everyone to change their password on their next login/visit.
You don't even need to ask people to change their passwords; when they login, you have a copy of the original password, so you can just store the new hash over the old.
