In this paper we study the optimal dividend payments for a company of limited liability whose cash reserves in the absence of dividends follow a Markov-modulated jump-diffusion process with positive drifts and negative exponential jumps, where parameters and discount rates are modulated by a finite-state irreducible Markov chain. The main aim is to maximize the expected cumulative discounted dividend payments until bankruptcy time when cash reserves are nonpositive for the first time. We extend the results of Jiang and Pistorius [15] to our setup by proving that it is optimal to adopt a modulated barrier strategy at certain positive regime-dependent levels and that the value function can be explicitly characterized as the fixed point of a contraction.