Unless the domain is penalized or a Flash site (cringe) or something, start with what your client has - there's probably some age and authority attached to it. If there are glaring PROBLEMS with the site (canonical errors, thin content, spammy use of keywords, useless or spammy page titles) fix those. Start talking redesign if the site's really dated or hard to use (plan for mobile-friendly if you do) but doesn't need to be your first priority. Don't go blowing away pages until you see if there are any decent links in to them, and redirect them to similar content if need be.
Have you worked with local search before? Although traditional web factors have become more important lately, there's a lot of groundwork you can do which has nothing to do with the web site - assuming at least some keywords bring up a map "pack" of local listings. A good Google mybusiness page, citations (if you're lucky, they're non-existent and you have a clean slate to work with. If your client has ever used call-tracking numbers or moved they're probably a hot mess), reviews ... Get started with that. Depending on the market he's in and how local his business is, that in itself can jumpstart his visibility.
It takes time, regardless so manage your client's expectations.