Yes, the laptop is likely to be overheating and the thermal protection system is slowing it down to protect the hardware. Get the fan replaced as soon as possible and try not to use the laptop in the meantime.

How do you know its the Fan and not the Hard Drive that's the Problem

I would say that your fan is ok but your laptop needs to be serviced. This involves stripping down the machine, cleaning the vents & fan. The processor, graphics chip & heatsink is also cleaned & new thermal paste added. This operation will most certainly fix your overheating laptop.

.. compaq presario around 6 years old ..

After six years of use it is very likely you have a lot of dust/fluff around the fan an cooling ducts/fins as spiderlegz indicates. You really have only two options, to do it yourself or get it serviced.

If you want to have a go yourself, there is a video which may help and a simple suggestion here.

Personally I would be tempted to do the minimum of disassembly and use a vacuum cleaner to remove as much dust/fluff as possible. Obviously the laptop must be switched off and care taken when using the vacuum not to do any damage.

For the future the is a site that offers quite a bit of varied information on working on laptops here.