Martin Fowler says that we should do refactoring before adding new features (given that the original program is not well-structured).
So we all want to refactor this dirty codebase, that's for sure. We also know that without unit-testing code it's very easy to introduce subtle bugs.
But it's a large codebase. Adding a complete suite of tests to it seems impracticable.
What would you do in this case?
I agree with the others, touch as little as possible. But, also, you can always start writing unit tests for new functionality and/or existing functionality that you'll be touching. No one said you need to write unit tests to test 100% of the existing code base to start with.
Let me recommend the book Working effectively with legacy code by Michael Feathers. It contains a lot of realistic examples and shows good techniques for tackling the legacy code beast.