It does sound as if the supply volts for your fan on your motherboard have packed up. It's also likely in that case that your original fan is probably OK. Or both fans are knackered
Assuming your new fan is OK, you're going to have to power it from the main Power Supply. This means either getting a 3 pin to 4 pin Molex adaptor or cutting off the 3 pin plug and wiring it to an old Molex plug via a terminal block.
You need to come off the 12 volt supply, the 12V+ wire is usually yellow and any of the two middle black wires will be your 0V (minus).
If you have a voltmeter it's worth checking the volts before you connect, although you can't really go wrong. If you connect to the 5 volt rail, your fan will go slow, if you get the wires round the wrong way I believe the fan will just rotate the wrong way.
Not entirely sure on that last bit though