Post-operative complications have a significant impact on patient morbidity and mortality; these impacts are exacerbated when patients experience multiple complications. However, the task of modeling the temporal sequencing of complications has not been previously addressed. We present an approach based on Markov chain models for characterizing the temporal evolution of post-operative complications represented in the American College of Surgeons National Surgery Quality Improvement Program database. Our work demonstrates that the models have significant predictive value. In particular, an inhomogenous Markov chain model effectively predicts the development of serious complications (coma longer than a day, cardiac arrest, myocardial infarction, septic shock, renal failure, pneumonia) and interventional complications (unplanned re-intubation, longer than 2 days on a ventilator and bleeding transfusion).