Markov models provide a natural framework for modeling cellular and molecular level changes over time. Kalbfleisch and Lawless propose using a Chi-squared statistic for assessing the appropriateness of assuming a first-order, homogeneous Markov process. While this statistic provides a global test of the Markov assumption, it does not permit identification of individual departures. We consider two approaches for discovering specific departures from the Markov assumption. First, we propose a diagnostic that tests whether the number of observed transitions out of a given state at a given time point is different than expected. Second, we construct statistics based on the number of observations in each state at each time point. In both cases, we construct multiple correlated statistics and testing is achieved through simulations. These approaches are applied to HIV genetics sequences measured over time.