First: Overheating a BMW engine is one if the worst things you can do to it. Overheating is stressful, has the potential to destroy gaskets and if severe enough can warp heads or totally kill the engine. Very bad.

What components you should replace will depend upon what the maintenance/repair history of your car. The entire cooing system on E60s (water pump, thermostat, hoses, coolant expansion tank) are prone to failure after 70K miles. Any one of the components can leave you stranded on the side of the road. If you allow them to fail one at a time you repeatedly risk overheating the car. And experience tells us that the parts become so brittle from age and heat that just handling components in the cooling system while repairing others can lead to their failure shortly thereafter.

Labor, whether your time or a mechanic's, is valuable. Replace all coolant system components at the same time except for components you know are good (for instance if you have replaced the coolant expansion tank 5,000 miles ago). And unless you been replaced the serpentine and AC belts recently, replace those while they are off.

Hopefully you have a good Indie, or can find one close to you as the dealers are very expensive for this type of work. DIY is best if you can turn a wrench. There are all kinds of DIY procedures on this forum if you do a search.

My 2004 545i is about to hit 80k and the water pump is done. Rattling bearings on the impeller shaft. I will be replacing it myself along with the thermostat. (It looks like the previous owner already did the belts and hoses.)

For water pumps look into stewarts

i just replaced the water pump at 102k miles. the bearing went all at once.. had the car towed home. thermostat & coolant tank went out around at 86K. Replaced the water pump and the ac belt was a pain but I was able to walk it back by turning over the crank with a breaker bar.

All back together and ready to sell it. its a 2004 545i 102k miles fully load. I plan to ask 12K for it then picking up a 2011 535i.

Once a car leaves me stranded and I have to tow it home its time to get rid of it.. nuff said

I recently replaced the water pump on '04 545 at about 114k miles due to coolant leak out of weep hole. Worst part of job is crank pulley removal/installation because you have to remove and install bolts blind. Also installation of a/c stretch belt is no fun.

Mine just let go at 154k. I have a 04 545.

Mine blew on me while doing about 80mph on the freeway, had I been on any sort of curvy road, I would have most definitely wrecked my car. Had it happened only another mile further on my route, I would've been on such a road. Luck and quick reflexes are the reason Im here today. After repairing several coolant leaks in multiple places before the pump actually went, I should've proactively replaced the pump. In my neck of the woods, it took about a week to get a replacement pump with a metal impeller. So my car sat in the parking lot at work for close to a week. VERY FRUSTRATING.
BLUF: I would not recommend any one to wait especially if your mileage was as high as mine was (112k).

Basic tools. .. go to pelican parts web and look at diy. .. pic by pic instruction. ..as above. ..all hoses...belts and expansion tank recommended

just changed mine out at 75k miles

an update to my own thread, so when i posted this back in 2012, I had 81k miles. The water pump finally failed on me at 105k miles back in Feb 2015.