In this paper we develop a new method to value American stock options with stochastic interest rates. We construct a binomial tree for the stock price divided by the price of the zero coupon bond that matures at the maturity date of the option. In fact, we construct a tree for the so-called forward risk adjusted measure. In each node of the tree the quotient of the stock price and bond price is constant and there are combinations of stock and bond prices for which immediate exercise is optimal and other combinations for which this is not the case. We derive for each node in the tree an analytic expression for the expected immediate exercise premium conditional on this quotient of stock and bond prices. This immediate exercise premium is added to the value that is derived from the familiar backward procedure. Both European and American option prices depend on the correlation between the interest rate process and the stock price process. It is interesting to see that with increasing correlation between the interest rate process and the stock price process, and hence a decreasing correlation between bond and stock prices, the values of European options increase, while the values of the early exercise premium decrease. For American options this might result in a non-monotonic relation between the correlation coefficient and the option price. Furthermore, there is evidence that the early exercise premium due to stochastic interest rates is much larger than established before by other researchers. Finally, we also consider the influence of the shape of the initial term structure.