Visual inspection might help too. I had a PSU fan lose a blade, most obvious when peering into the block (harder than observing a CPU/etc fan, except maybe the ones on a perpendicular graphics card, slotted in, with its plastic manifold guiding air from/to the rear plate) when powered off, and carefully prodded round with something (non-conducting and otherwise not totally unsuitable).
I repaired that one myself by opening it up (*beware of latent high charges*, mostly but not entirely in the mains-side parts of the PSU - not as dangerous as messing with CRT electronics, but I'm still not recommending it as something everyone could do) and finding an equivalently-sized fan in Maplins (now closed), our Radio Shack equivalent.
Shortly after recommissioning, I heard the a PC fan suddenly whir up to a previously not experienced speed. Shut it down and found that the CPU fan, this time, had broken. At the spindle. It had disconnected from the blades around it (still as a whole) and with virtually no air-moving load or detected cooling effect, it had gone to the maxest of max speeds. Another trip to Maplin and one (far more trivial) fan-replacement later, that machine was working again. If I hadn't been there, I imagine it was at risk of having ended up with a fried chip, but I was lucky.
(Still is. 15-or-more years later, working 24/7/52.1767857 for almost all that time apart from weekly soft-reboots to prevent OS-related memory-leak crud from building up in its ?16?Mb RAM. Except that the last time I fully shut down and restarted this machine (to hoover its internals of dust) it seems the CMOS cell needs replacing. That'll wait for the next dust-down, though.)
So, erm. Yeah. Look at the bits and pieces, even when not running you might see something wrong with a fan. Though it may be either a hidden issue (part-worn ball(s) in an internal bearing-ring, not worth digging into beyond replacing with fan assembly as a whole, dependant on it being one of those generic X-mm black square-framed fans or not) or the mechanics might be working perfectly, and it's either a build up of dust restricting the air-flow efficiency (suck/blow it away, with or without mechanical prodding/brushing/scraping, maybe) or even an imperfect connection of fan/heatsink to to whatever hot bit that f/h is servicing, and until you get it properly thermally reattached (however it needs it) it's just trying to do more work because the sensors know it isn't actually cooling like they think it should be.
This may sound daunting, but only because it could be loads of little things, from trivial to maybe-you-want-to-get-a-professional-in level, and we can only cover some of those as suggestions. With any luck it'll be towards the low end of that spectrum. And easily proven to be, too.