What is a good approach to starting a really big project?

I've recently been challenged with a very hefty redesign for a major financial tool. Most everything about this application is a mess. (They've been building it for the last 10 years, and I'm the first designer they've hired.)

The logic is very complex, nothing is organized, and nothing is standardized. There are so many problems to fix, it's hard picking the worst one. (There's no help system, no navigation system, and there are a TON of ugly/unusable forms.)

So, my question is this: for large / complex redesigns, where do you start? Any useful tips for planning a major redesign?

Thanks!

Edit: For my specific case, end users are out of my reach. (I work in banking -- security issues...) I'd prefer to keep answers general, but it would also be helpful to touch on what you guys would do if you couldn't access users directly. Also, this is a back end system -- not a consumer facing website. It's only used by high-profile companies / bank account managers.