How I have dealt with it:
1. Never complain. Never bad mouth any of my predecessors. Whatever they did wrong, I probably did somewhere else just as badly. We all have.
2. Never be bashful about what is wrong. Be objective. Be specific. Keep asking questions until there are no more answers.
3. Become the new expert. Don't depend on "higher-ups" for too much judgement. Convincing them should be about as hard as convincing a mother that her bleeding child needs a band-aid. If they need convinced, they are part of the problem.
4. Long conference room tables, paper, scotch tape, and multiple colored highlighters are your friend. Others thought I was crazy, but I have had to paper table and walls with technical debt to a) understand better and b) have everyone visualize what we're up against.
5. Don't be afraid to rewrite anything with a couple of caveats: a) Do it in less that a week. b) Do it only to understand it. Plan to throw away what you rewrite. c) If you can use what you wrote instead of what's already there, that's gravy.
6. Priority of what to learn: a) The data base. b) The code. I have even written utilities to scan and label data to understand what the hard disk looks like before ever venturing into the code mess.
7. Priority of things to refactor/rewrite: a) Rename variables EXACTLY what they are. This can be very difficult but will probably give you the biggest bang for the buck. This step often opens the flood gates for everything else. b) Remove duplicate code and modularize. c) Reduce long conditionals. 800 line case statements suck. d) Remove early exits. The idea is not to improve the performance of the code, it's to understand what it's doing. Multiple exits can be very confusing. e) Fix white space, maybe more, maybe less. The process of doing these things almost always provides better learning that just reading it. Sometimes I have had to rewrite something and then throw it away just to understand what we have.
8. By the time you reach this step, you probably know more about what we've got, what our problems are, and what the speed bumps will be in the future. You probably won't have to convince anyone to do anything except come to start seeing you as an excellent resource.
9. Bitch about all of the above at home at night. You may ruin your marriage, but at least you'll still have a job.