Hi! I have almost two decades experience in software development, most of which I spent fixing projects like the one you mentioned.

TLDR: this is hard

The biggest mistake people make (yeah, I made it too) is to quickly loose credibility with stakeholders by not providing visible value or by increasing failure rate.

Before you even start the project, you need to communicate with stakeholders and discuss what are their problems and how you are going to address them.

You also need to get very familiar with the codebase. You need to understand various patterns that are hurting it, what is their effect (are they just cosmetic problem, are they hurting reliability? maintainability?). You then need to create a step by step plan that will address those problems starting with removing the problems that are causing biggest issues, are prerequisites to resolving other issues and are least risky to deal with.

Remember, on any project like that you are spending your trust you have with the stakeholders. The more trust you have and the less expenditure rate the longer you will be able to work with.

Try to figure out how you can bring some real visible improvements at the very start of the project to build your credibility and then a string of even small successes along the line so that stakeholders are kept in positive mood.

Plan hard to avoid failures as the mood may change quickly to "why are we even doing this" when stakeholders are in hot water with their clients.

Choose KPIs and measure them throughout the project to give visible feed on your improvements to your managers.

On the technical side, it will be critical to have good development process. Automate delivery mercilessly early on -- this is key to keep failure rate in check and allow you to work at required velocity but more importantly, it is a visible improvement that you can show to your customer to build your credit of trust.

Touch the code as little as possible. Only try to fix the big problems that you have identified. If you start messing around too much you may introduce failure when fixing stuff that wasn't worth the risk and you also risk alienating other people that are working with the code base. Remember, you are making everything more difficult for them already, don't make it more difficult than necessary.

My most recent project was a mess of hundreds of components, 400k of extremely low quality code. Instead of jumping right away into fixing the code I have spent time talking to stakeholders and to what their problems were (not what I was thinking). I then quickly addressed their problems. The existing team wasn't prioritizing it highly because they didn't even know it was important... I then observed that with the existing development process I will never be able to deliver this many changes with acceptable failure rate, so I started by working on automating build, deployment and testing. Early on I identified that the high complexity of the project meant people were having hard time doing anything reliably. So I quickly prioritized reducing complexity over fixing bad architectural patterns. This helped my peers working on the code and further helped me fuel positive image of the change.