In this paper, we describe Dynamic Probabilistic Ontology Trees, a new probabilistic model to track dialog state in a dialog system. Our model captures both the user goal and the history of user dialog acts using a unified Bayesian Network. We perform efficient inference using a form of blocked Gibbs sampling designed to exploit the structure of the model. Evaluation on a corpus of dialogs from the CMU Let's Go system shows that our approach significantly outperforms a deterministic baseline, exploiting long N-best lists without loss of accuracy.