Start by adding integration tests, then (try to) identify the core of the project and isolate that in its own sub-project in the repo. Add unit tests for the functions in the core and then split the remainder into parts that are peripheral and that could be removed/disabled. (say a spellchecker). Next up re-factor the core until you're happy with the state of affairs, but keep the interface the same. If there was no interface to the rest of the code then you'll need to define one and implement that as well as changing the peripheral code to use that interface. Then look at each peripheral piece and decide if it is worth saving, needs rebuilding or refactor it as well.
The basic trick is to reduce scope until a subsection of the work becomes tractable.
With a really large project this is a multi-year effort with a team of seasoned programmers, it's hard and it means that while you do it there will be no honoring feature requests. You need management buy-in, patience and perseverance but that goes for any large effort.
Building fresh and green stuff is obviously much more fun to do but taking an old codebase and making it nice is (to me, at least) just as rewarding.