In this research, a reliability-based optimization model of bridge maintenance and replacement decisions is developed. Bridge maintenance optimization models use deterioration models to predict the future condition of bridges. Some current optimization models use physically-based deterioration models taking into account the history of deterioration. However, due to the complexity of the deterioration models, the number of decision variables in these optimization models is limited. Some other optimization models consist of a full set of decision variables; however, they use simpler deterioration models. Namely, these deterioration models are Markovian, and the state of the Markov chain is limited to the condition of the facility. In this research, a facility level optimization model of bridge maintenance and decisions is developed, using a Markov chain whose state includes part of the history of deterioration and maintenance. The main advantage of this formulation is that it allows the use of standard optimization techniques (dynamic programming), while using realistic, history-dependent deterioration models. This research presents a method to formulate a realistic history-dependent model of bridge deck deterioration as a Markov chain, while retaining relevant parts of the history of deterioration, using state augmentation. This deterioration model is then used to formulate and solve a reliability-based bridge maintenance optimization problem as a Markov decision process. In a numerical example, the policies derived using the augmented Markov chain are applied to a realistic bridge deck, and compared to the policies derived using a simpler Markov chain. Copyright ASCE 2006.