•General framework for approximating time-changed Markov processes.•Flexible approach, including three Markov chain approximation strategies.•Accommodates time-changed (subordinated) Levy and diffusion processes as special cases.•Pricing for American/Bermudan options, European options, and variance swaps. In this paper, we propose a general approximation framework for the valuation of (path-dependent) options under time-changed Markov processes. The underlying background process is assumed to be a general Markov process, and we consider the case when the stochastic time change is constructed from either discrete or continuous additive functionals of another independent Markov process. We first approximate the underlying Markov process by a continuous time Markov chain (CTMC), and derive the functional equation characterizing the double transforms of the transition matrix of the resulting time-changed CTMC. Then we develop a two-layer approximation scheme by further approximating the driving process in constructing the time change using an independent CTMC. We obtain a single Laplace transform expression. Our framework incorporates existing time-changed Markov models in the literature as special cases, such as the time-changed diffusion process and the time-changed Lévy process. Numerical experiments illustrate the accuracy of our method.