Existing nonlinear optimization-based algorithms for estimating Markov transition probability matrix (TPM) in bridge deterioration modeling sometimes fail to find optimum TPM values, and hence lead to invalid future condition prediction. In this study, a Metropolis-Hasting algorithm (MHA)-based Markov chain Monte Carlo (MCMC) simulation technique is proposed to overcome this limitation and calibrate the state-based Markov deterioration models (SBMDM) of railway bridge components. Factors contributing to rail bridge deterioration were identified; inspection data for 1,000 Australian railway bridges over 15 years were reviewed and filtered. The TPMs corresponding to a typical bridge element were estimated using the proposed MCMC simulation method and two other existing methods, namely, regression-based nonlinear optimization (RNO) and Bayesian maximum likelihood (BML). Network-level condition state prediction results obtained from these three approaches were validated using statistical hypothesis tests with a test data set, and performance was compared. Results show that the MCMC-based deterioration model performs better than the other two methods in terms of network-level condition prediction accuracy and capture of model uncertainties.