The discrepancy between observations from gamma-ray astronomy of the Fe-60/Al-26 gamma-ray flux ratio and recent calculations is an unresolved puzzle in nuclear astrophysics. The stellar beta-decay rate of Fe-59 is one of the major nuclear uncertainties impeding us from a precise prediction. The important Gamow-Teller strengths from the low-lying states in Fe-59 to the Co-59 ground state are measured for the first time using the exclusive measurement of the Co-59(t, He-3 + gamma) Fe-59 charge-exchange reaction. The new stellar decay rate of Fe-59 is a factor of 3.5 +/- 1.1 larger than the currently adopted rate at T = 1.2 GK. Stellar evolution calculations show that the Fe-60 production yield of an 18 solar mass star is decreased significantly by 40% when using the new rate. Our result eliminates one of the major nuclear uncertainties in the predicted yield of Fe-60 and alleviates the existing discrepancy of the Fe-60/Al-26 ratio.