I once did a major cleanup at the start of my career. The above advice is closest to what proved successful to us, together with the response by JohnBooty https://news.ycombinator.com/item?id=17825093.
In our case, I think we didn't write a lot of tests, because we didn't know they're so useful then. But much later I did a few ports of FOSS software between programming languages, and comprehensive test suites were absolutely godsend in those cases. So, if you can, try to write tests as first thing indeed.
Other than that, we took a kind of "organism fighting a cancer" approach. In a spaghetti codebase, we tried to find some smallest possible islands of the most isolated code (a lot of detectivistic work). Then try to improve the isolation even more — slowly engulfing the "tumor" in a more reasonable API. Once we had a somewhat acceptable API, with mostly well understood semantics, rewrite the internals of the tumor from scratch. Rinse and repeat.
Notably, as mentioned by JohnBooty, we did talk this with management. It made our product release late by ~1yr. The argument was that there was a particular critical bug, which would result in lost consumer data. This one bug was found very close to original release date, and opened our eyes to the horrors in the codebase (actually, a big part written by a subcontractor).
Sorry if the reply is somewhat chaotic, I didn't have much time to write it.
EDIT: Also, I believe the term "technical debt" is reasonably good when talking with management/owners, as it has correct connotation of an investment at early stage, which however has to be repaid later at a cost.
In our case, I think we didn't write a lot of tests, because we didn't know they're so useful then. But much later I did a few ports of FOSS software between programming languages, and comprehensive test suites were absolutely godsend in those cases. So, if you can, try to write tests as first thing indeed.
Other than that, we took a kind of "organism fighting a cancer" approach. In a spaghetti codebase, we tried to find some smallest possible islands of the most isolated code (a lot of detectivistic work). Then try to improve the isolation even more — slowly engulfing the "tumor" in a more reasonable API. Once we had a somewhat acceptable API, with mostly well understood semantics, rewrite the internals of the tumor from scratch. Rinse and repeat.
Notably, as mentioned by JohnBooty, we did talk this with management. It made our product release late by ~1yr. The argument was that there was a particular critical bug, which would result in lost consumer data. This one bug was found very close to original release date, and opened our eyes to the horrors in the codebase (actually, a big part written by a subcontractor).
Sorry if the reply is somewhat chaotic, I didn't have much time to write it.
EDIT: Also, I believe the term "technical debt" is reasonably good when talking with management/owners, as it has correct connotation of an investment at early stage, which however has to be repaid later at a cost.