We estimate the decay of correlations for some Markov maps on a countable state space. A necessary and sufficient condition is given for the transfer operator to be quasi-compact on the space of locally Lipschitz functions. In the non-quasi-compact case, the decay of correlations depends on the contribution to the transfer operator of the complementary of finitely many cylinders. Estimates are given for some non-uniformly expanding maps and for maps with bounded jumps.