Pavement structures are constantly deteriorating due to many distresses, for instance cracks and rutting that are initiated and expanded. Deterioration models of pavement structures is an important component of pavement management systems (PMS). The deterioration of pavements has been extensively modeled using Markov chains. This paper aims at formulating a more efficient deterioration model to predict the condition of pavement sections. It is proposed to accomplish this by developing a Markovian deterioration model coupled with a meta-heuristic search optimization method, namely genetic algorithms (GA). An essential component of the Markov chain model is the transition probability matrix. In the proposed model, a standard percentage prediction method was used to calculate the transition probabilities. This is then calibrated by integrating the GA method with the Markov chain. The model is based on the historical international roughness index (IRI) data retrieved from the long-term pavement performance (LTPP) database. To test the validity of the method, a real-life case study is used and the performance of the developed model was assessed using both validation and testing data. For predicting pavement conditions, this study concluded that calibrating calculated transition probabilities using meta-heuristic optimization results in better performance than developing the transition probabilities using classical methods. The Markovian-GA model developed in the present study can be used to predict the future condition of pavement facilities in order to assist engineers in planning the optimum maintenance and rehabilitation (M&R) actions.