ASUS Radeon 4870 HD, Fan has stopped working.

Check that the power cable from the PSU to the card is properly seated at both ends.

Also check that the card is correctly seated in the PCIE slot.

Also, when powered down, see if you can move the fan with your fingertip - It may just be jammed on something.

This happened to my card also.

It was jammed when i cleaned it.

Just move the fan a bit as mockingbirduk said  

I gave the fan a quick clean and there seems to be no obstruction, I also checked the power and there seems to be nothing wrong there. Would installing a new GPU fan be an option?

Cheers for the Replies  

You could try RMAing the card and get another one.

I only say this because you don't know the damage the high temps did to your gpu. Try and get it replaced and have a piece of mind.

Before spending any money i would try to troubleshoot with a few more options...Maybe try your card in a buddy's PC to rule out your computer having any issues besides this gpu's fan. You could also try another card in your PC to rule out that your motherboard or PSU or anything else is the culprit here. And lets say you did rule out these things and it seems your gpu has a problem there are obviously VGA coolers that can replace the current stock(?) fan on it now but those from what ive seen arent that cheap. Now this is assuming you have no warranty or you over clocked or w/e and you voided your warranty or blah blah blah  

Just troubleshoot until you know for sure what it is and you could even go as far as removing your gpu's heat sink/fan and reattaching it after inspecting the undercarriage of the heat sink. But you definatly want to buy some thermal paste before doing that as you would have to reapply that or make a coffin for your gpu LOL

hope this helped  

RMA the card.

If it's still under warranty, RMA it. If it's not, there are some excellent 3rd-party replacement GPU coolers available.