Air pollution is a matter of concern among the public, especially for those living in urban and industrial areas. Markov chain modeling is often used to model the underlying dynamics of air pollution, which involves describing the transition probability of going from one air pollution state to another. Thus, estimating the transition probability matrix for the data of the air pollution index (API) is an essential process in the modeling. However, one may observe many zero probabilities in the transition probability matrix, especially when faced with a small sample, interpreting the results with respect to the climate condition less realistic. This study proposes a robust empirical Bayes method, which incorporates a method of smoothing the zero frequencies in the count matrix, contributing to an improved estimation of the transition probability matrix. The robustness of the empirical Bayesian estimation is investigated based on Bayes risk. The transition probability matrices estimated based on the robust empirical Bayes method for the hourly API data collected from seven monitoring stations in Malaysia for the period 2012 to 2014 are used for determining the air pollution characteristics such as the mean residence time, the steady-state probability and the mean recurrence time. Furthermore, the proposed method has been evaluated by Monte Carlo simulations. Results suggest that it is quite effective in producing non-zero transition probability estimates, and superior to the maximum likelihood method in terms of minimizing the mean squared error for individual and entire transition probabilities. Therefore, the robust empirical Bayes method proves to be an improved approach to the estimation of the Markov chain. When applied to API data, it could provide important information on air pollution dynamics that may help guiding the development of proper strategies for managing the impact of air quality.Supplementary Information: The online version contains supplementary material available at 10.1007/s40201-020-00607-4.