OK, with a 4870 (I'm jealous by the way) there is no way that SoaSE will be asking too much from it. It should barely need to turn the fans.
It could be the exact opposite, particularly if you have turned the graphics options down.
Some games can end up overheating a graphics card by asking it to do too little. It sounds nuts I know but with the card doing little or no real work it ends up shoving frames out so fast that it overheats just from the massive frame rates (I'm oversimpliying a bit, but thats the gist of it).
GalCiv 2 had this problem and had to introduce a throttling option to the graphics settings.
A few things to try:
1) Make sure you are using the "Application defaults" (or whatever the equivalent is) from the graphics cards own display settings. Especially do not force it to turn off vertical sync.
2) The 4870 is a dual card in a single slot (if Im not mistaken), so turn OFF Crossfire mode for this game. You probably don't actually need it for SoaSE and some games don't like it anyway.
Edit: Scratch that last one - sorry it's the 4870X2 that's a dual card.
3) Turn the games graphics settings up to their max - that card can take it, no bother - enjoy.
Also do the memory and power supply tests that others suggested.