Hidden Markov Models (HMMs) have become increasingly popular in recent years in a wide range of applications. Special subclasses of HMMs have been extensively studied in various contexts. In this work we give a necessary and sufficient condition for a partially exchangeable sequence to be a countable HMM, i.e. a countably valued HMM with countable state space Markov chain. More precisely we show that a partially exchangeable sequence is a countable HMM if and only if it is a countable mixture of Markov chains. Our main theorem extends an old result of Dharmadhikari which proved that an exchangeable sequence is a countable HMM if and only if it is a countable mixture of i.i.d. sequences. The main technical tool we use to generalize Dharmadhikari's theorem is the Diaconis-Freedman extension of de Finetti's theorem to partially exchangeable sequences. It seems interesting to deepen the understanding of the connection between HMMs and mixtures of Markov chains, models widely used in applications, as this could lead to new approaches to solve inference problems for both classes. In particular the problem of estimating the memory of a mixture of Markov chains has motivated us to investigate the connection between HMMs and partially exchangeable stochastic sequences.