Really you should have those tests upfront. After that noone should be scared of changing any part of the codebase. Let alone 'never' changing stuff.

Releasing rewrites / redesigns behind a feature flag, with a couple of strategic if statements is usually good enough. Noone cares that you had to change code outside of your interface for a release or two.