We study the structure of optimal causal encoder for a kth order Markovian source, minimizing the total rate subject to a mean-square distortion constraint. In our setup, the source has a general alphabet and the encoder is allowed to be variable-rate. This leads to an optimization problem in an infinite-dimensional space, for which we prove the existence of a solution. We further show that, for k > 1, the optimal causal encoder for a kth order Markovian source uses only the last k source symbols and the information available at the receiver. For k = 0, however, the optimal causal encoder is memoryless. We also consider the infinite-horizon problem, and provide an existence result for an optimal stationary solution. We further show that for coding of a linear source, the quantization of the innovation is an almost optimal scheme in the limit of low-distortion.