Fuzzy Time Series (FTS) models are commonly used in time series forecasting, where they do not require any statistical assumptions on time series data. FTS models can handle data sets with a small number of observations or with uncertainty. This is a general advantage of FTS as compared with other techniques. However, FTS models still have some criticisms, such as the optimal lengths of intervals and the proper weights, which always influence the model accuracy and still have been of many concerns in literature. The work in this paper proposes a novel FTS forecasting model based on a new tree partitioning method (TPM) and Markov chain (MC), called FTSMC-TPM, for determining the optimal partitions of intervals and the proper weights vectors respectively, and this will greatly improve the model accuracy. The efficiency of the FTSMC-TPM model is tested using two types of time series consisting of the air pollution index (API) data, which is collected from Kuala Lumpur, Malaysia and the benchmark data of the yearly enrollments for the University of Alabama. Three statistical criteria have been used for investigating the accuracy of the proposed model. The results indicate that the proposed model outperforms the existing classic and advanced time series models in terms of forecasting accuracy. In addition, the proposed model shows the ability to successfully deal with forecasting problems to obtain higher model accuracy, which is examined in comparison with the existing models to validate its superiority. Hence, this study demonstrates that the proposed model is more suitable for the accurate prediction of air pollution events as well as for forecasting any type of random time series. © 2013 IEEE.