Although you’ll probably find good approaches to working with poorly-designed spaghetti code in the question that Kilian Foth linked to in the comment, since you’re specifically interested in testing, there is a very specific solution.

This is the kind of problem that characterization tests were designed to solve. When you can’t test your functions and classes independently in well-defined units, you can write higher-level tests that capture the current behavior of the software. This can give you the confidence that you need to refactor the code behind the public interface. You may want to introduce something like a facade or adapter to keep your expected public interface while doing the refactoring and testing against that public interface. As you refactor and introduce more testable units, you can add additional unit and integration tests and phase out the characterization tests.

Write unit tests for whatever “Unit” or “Module” there is. If everything is tightly coupled to everything else, then you are kind of forced to treat it all as a single “unit”, and write your tests for your whole program.

An important part of automated testing is to clarify and document the current behavior of your program, so you know if refactoring introduce any regressions. Note that automated testing is not the only way to do this, you could also create manual tests, or write comprehensive documentation/specifications. It is also possible the current behavior diverges from the specified behavior, and that would be of particular note.

Keep in mind that the “unit” in unit testing does not necessarily mean a single class, “units” can be of any size. The important thing is that the unit has high cohesion and low coupling. It would be common to have tests at multiple levels of abstraction.

As you start restructuring the code you likely want to continue writing tests as you go, as soon as you manage to chop of some piece of functionality, write unit tests for that part so you know it won’t break later on.

A final point is that you want to test the “public behavior” of the unit you are testing, and try to avoid relying on anything implementation specific that might be subject to change. This can make it much more difficult to write acceptance criteria. As an example, think about how you would test a pseudo random number generator, without making any particular assumption about its internal algorithm.

As an addition to Thomas Owens’ nice answer, I think there are often opportunites to start with adding unit tests whenever you have a requirement to change something. Let’s say you already expect for a new requirement the need to add some more code to an already too-long function in some module.

Before you start refactoring the function, think about which part could be refactored to a smaller function, so it would make adding the new requirement afterwards easier. Then copy (!) the related part into a new module and/or function, write several unit tests for the copy and make sure it works as intented – in isolation. Maybe you can already extend this new function or module in a way it will support parts of the new requirements.

After you are pleased with the new function’s quality and have some confidence in it, you start refactoring the old code, and remove the parts which are now superfluous by calling the new function from the old code. Of course, at that time you should have the characterization tests in place suggested by Thomas.