In this paper a general numerical method for pricing American options in jump-diffusion models of stock dynamics with stochastic interest rates is developed. The time derivative and infinitesimal generator of the process for factors that determine the dynamics of the interest rate are discretized. The result is a sequence of embedded perpetual options in a Markovmodulated Lévy model. Options in this sequence are solved using an iteration method based on the Wiener-Hopf factorization. An explicit algorithm for the case of positive stochastic interest rates driven by a process of the Ornstein-Uhlenbeck type is derived. The efficiency of the method is illustrated with numerical examples.