Developing statistical models for air pollution forecasting is crucial for managing air quality. Nevertheless, many researchers have concentrated on improving the model�s accuracy when applying for data with many fluctuations in the pollutant�s concentration. Also, they have attempted to address the uncertainty analysis that might lead to inadequate outcomes. The fuzzy time series (FTS) is considered one of the powerful models that are commonly applied in predicting air pollution. However, most FTS models are not accurate in partitioning the universe of discourse. Therefore, a new hybrid model based on the FTS-based Markov chain and C-Means clustering technique with an optimal number of clusters is proposed in this study. This hybridization is contributed to produce an adequate partition and improve the model accuracy accordingly. The superiority of the proposed model is validated using three common statistical criteria. The PM10 concentration data collected from Melaka, Malaysia is used in this study. Results prove that the proposed model greatly improved the prediction accuracy, for which it outperformed several fuzzy time series models. Hence, we have concluded that the model proposed is a good option for forecasting air pollution and any type of random data. © 2022, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.