Yes, the Windows partition has to be shrunk. You can't have them both on one parittion. I would suggest partition magic.
After you make empty space for Linux, make sure you have a swap partition (usually twice the amount of RAM on your computer) and a large /home partition for user home directories containing their settings and files. This way if something happens to the root partition home is safe.
BTW, welcome to LQ and the world of Linux