Multi-state models for event history analysis most commonly assume the process is Markov. This article considers tests of the Markov assumption that are applicable to general multi-state models. Two approaches using existing methodology are considered; a simple method based on including time of entry into each state as a covariate in Cox models for the transition intensities and a method involving detecting a shared frailty through a stratified Commenges-Andersen test. In addition, using the principle that under a Markov process the future rate of transitions of the process at times $t > s$ should not be influenced by the state occupied at time $s$, a new class of general tests is developed by considering summaries from families of log-rank statistics where patients are grouped by the state occupied at varying initial time $s$. An extended form of the test applicable to models that are Markov conditional on observed covariates is also derived. The null distribution of the proposed test statistics are approximated by using wild bootstrap sampling. The approaches are compared in simulation and applied to a dataset on sleeping behavior. The most powerful test depends on the particular departure from a Markov process, although the Cox-based method maintained good power in a wide range of scenarios. The proposed class of log-rank statistic based tests are most useful in situations where the non-Markov behavior does not persist, or is not uniform in nature across patient time.