best way to change address?

any way to do this successfully or just basically have to start over with local SEO?

Depends on the type of link building you've done. If you've built a lot of citations, then you will have to manually go through each directory and update your information one by one. In terms of Google, ,it should be as simple as updating your business profile, however, this won't translate to all the backlinks and directories you should have built for these types of links. So either way, you will need to do a lot of leg work to bring the site up to date.