usually, when i have the time for it ( ask management ) i start by writing missing tests for the legacy codebase ( which, more often than not, have very little automated tests ). Then, isolate and encapsulate the hell of it, to the point that it can be replaced more easily, if/when needed.

OTOH, when there is no time available for this kind of care, i just go rodeo-style, guns blazing, code crashing and long nights... fixing the most low hanging bugs, or the most critical.