Overheating is definitely a possibility, but that doesn't necessarily mean the fan needs to be replaced. There might just be too much dust in the heatsink and fan for there to be enough airflow to cool your CPU.
There could be other explanations too. How long does it take, usually? Do you see a blue screen right before it shuts off? Any other clues?