moritz,
The title doesn't really match what is being asked. A more appropriate title might have been "How to retrofit a test suite to a complex application". From that perspective, I might address the question from a different angle. The rest is meant more for the OP than for you - but it is meant in context of your response.

What are you hoping to accomplish? Do you have some significant changes coming up and you want to be sure you don't break anything? Do you suspect that over time the application has evolved and you are unsure if all the business requirements are being met? Perhaps you think there is a lot of "dead code" that can be pruned. Do you have the luxury of devoting yourself to this full time or do you need to take a more iterative approach?

Now that you know what your motivation is, is testing where you need to begin? There is a good chance that, if there is no test suite, then there is likely no or ill defined requirements. Backing into requirements can be as much "fun" as backing into testing. Since there are a myriad of different types of tests you can run (see Software testing), you will at a minimum want to make sure you are meeting your business requirements. If you can, don't look at or even think about your code when documenting these requirements.

Since this is an existing large and complex application, you can start by writing tests for individual subroutines. Keep your business requirements handy as a checklist. If the subroutine assumes some other function performed correctly, write the test that way too (even if you haven't looked at that code yet). In other words, don't be afraid to write a test that you know or are unsure will fail. The test is the correct behavior so failures will help you find bugs.

A missing test suite is an indicator of other problems (like lacking requirements). It may be beneficial to read through Re: Refactoring a large script to see if any of those other things apply as well.