A surrogate data analysis is presented, which is based on the fluctuations of the "entropy" S defined in the natural time domain [Phys. Rev. E 68, 031106 (2003)]]. This entropy is not a static one such as, for example, the Shannon entropy. The analysis is applied to three types of time series, i.e., seismic electric signals, "artificial" noises, and electrocardiograms, and it "recognizes" the non-Markovianity in all these signals. Furthermore, it differentiates the electrocardiograms of healthy humans from those of the sudden cardiac death ones. If deltaS and deltaSshuf denote the standard deviation when calculating the entropy by means of a time window sweeping through the original data and the "shuffled" (randomized) data, respectively, it seems that the ratio deltaSshuf /deltaS plays a key role. The physical meaning of deltaSshuf is investigated.