This paper presents a novel extension of Hidden Markov Models (HMMs): type-2 fuzzy HMMs (type-2 FHMMs). The advantage of this extension is that it can handle both randomness and fuzziness within the framework of type-2 fuzzy sets (FSs) and fuzzy logic systems (FLSs). Membership functions (MFs) of type-2 fuzzy sets are three-dimensional. It is the third dimension that provides the additional degrees of freedom that make it possible to handle both uncertainties. We apply the type-2 FHMM as acoustic models for phoneme recognition on TIMIT speech database. Experimental results show that the type-2 FHMM has a comparable performance as that of the HMM but is more robust to noise, while it retains almost the same computational complexity as that of the HMM.