Goodness-of-fit tests are useful in assessing whether a statistical model is consistent with available data. However, the usual chi-squared asymptotics often fail, either because of the paucity of the data or because a non-standard test statistic is of interest. In this talk, I shall describe exact goodness-of-fit tests for first- and higher-order Markov chains, with particular attention given to time-reversible ones. These tests will be obtained by conditioning on the sufficient statistics for the transition probabilities and will be implemented by novel Monte Carlo or Markov chain Monte Carlo sampling methods. These tests are applicable both to single and to multiple sequences and they allow a free choice of test statistic. I shall present a few applications. The first concerns multiple sequences of dry and wet January days for the years 1948 to 1983 at Snoqualmie Falls, Washington State. The second one is a reanalysis of a four-state DNA sequence. The last one focuses on a six-state atomistic dataset arising in molecular dynamics simulation of solvated alanine dipeptide. This work was done in collaboration with my late colleague Julian Besag.