We prove an analogue of Blackwell's renewal theorem or the "key renewal theorem" and the existence of the limit distribution of the residual waiting time in the following setup: $X_0, X_1, \cdots$ is a Markov chain with separable metric state space and $u_0, u_1, \cdots$ is a sequence of random variables, such that the conditional distribution of $u_i$, given all $X_j$ and $u_l, l \neq i$, depends on $X_i$ and $X_{i+1}$ only. Here the $V_n \equiv \sum^{n-1}_0 u_i, n \geqq 1$, take the role of the partial sums of independent identically distributed random variables in ordinary renewal theory. E.g. the key renewal theorem in this setup states that $\lim_{t\rightarrow\infty} E\{\sum^\infty_{n=0} g(X_n, t - V_n)\mid X_0 = x\}$ exists for suitable $g(\bullet, \bullet)$, and is independent of $x$.