First step is fixing the development environment / build process and getting a staging server up. It will inevitably be broken / nonexistent, with frequent edits directly to production necessary. The last guy will have internalized a great deal of operational workarounds that you'll need to rediscover then codify into the app.

Next you write tests. There will be none. Once you have a workflow that is decent, you can start to identify the worst offenders. All the while, you'll be having to change the codebase to meet project requirements, this will give you a good idea of where the really bad shit is. Unit test all of it, and if you're feeling froggy, write some integration tests. Once you get to this phase, you should be unit testing your project work.

Only after those two are completed can you start refactoring. Treat it like TDD. Keep an eye on larger goals like 12 factor conformance. It may look pie-in-the sky at first, but it will give you ideas on what to focus on. Main advantage of refactoring over ground-up re-writing is, you don't have to sell it to your boss. You just do it, in and around normal project work.

The biggest hurdle is the first step. It's scary to fuck with deployment. The approach I've come up with is to fork the codebase and rebuild the tooling on top of that, deploying first to staging, then to production, alongside the current working copies. Once you're satisfied flip the switch. You may have to flip it back, but at least it will be easy and instantaneous.

These lessons are from my ongoing project to modernize an ancient Rails 2.3.5 website running on Debian Lenny. Linode doesn't even offer that OS anymore, I had to cannibalize a server with an EOL app on it for a staging environment. I can't use Vagrant because there aren't any Lenny boxes.

It's long, arduous and slow. I fucking love it.