A way of statistically testing for nonlinearity in a time-series is to employ the method of surrogate data. This method often makes use of the Fourier transform (FT) in order to generate the surrogate. As various authors have shown, this can lead to artefacts in the surrogates and spurious detection of nonlinearity can result. This paper documents a new method to synthesize surrogate data using a Ist order hidden Markov model (HMM) combined with a Kolmogorov-Smirnoff test (KS-test) to determine the required resolution of the HMM. Significance test results for a sinewave, Henon map and Gaussian noise time-series are presented. It is demonstrated that KS-tested HMM surrogates can be successfully used to distinguish between a deterministic and stochastic time-series. Then by applying a simple test for linearity, using linear and nonlinear predictors, it is possible to determine the nature of the deterministic class and hence conclude whether the system is linear deterministic or nonlinear deterministic. Furthermore, it is demonstrated that the method works for periodic functions too, where FT surrogates break down. (C) 2001 Elsevier Science B.V. All rights reserved.