This paper develops an a.s. convergence theory for a class of projected Stochastic Approximations driven by finite-state Markov chains. The conditions are mild and are given explicitly in terms of the model data, mainly the Lipschitz continuity of the one- step transition probabilities. The approach used here is a version of the ODE method as proposed by Metivier and Priouret. It combines the Kushner-Clark Lemma with properties of the Poisson equation associated with the underlying family of Markov chains. The class of algorithms studied here was motivated by implementation issues for constrained Markov decision problems, where the policies of interest often depend on quantities not readily available due either to insufflcient knowledge of the model parameters or to computational difficulties. This naturally leads to the on-line estimation (or computation) problem investigated here. Several examples from the area of queueing systems are discussed.