Sample entropy (SampEn) was reported to be useful in the assessment of the complexity of heart rate dynamics. Permutation entropy (PermEn) is a new measure based on the concept of order and was previously shown to be accurate for short, non-stationary datasets. The aim of the present study is to assess if SampEn and PermEn obtained from baseline recordings might differentiate patients with various outcomes of the head-up tilt test (HUTT). Time-domain heart rate variability (HRV) indices and several nonlinear parameters were calculated using 500 RR interval-long ECG recordings done before tilting in patients with a history suggesting vasovagal syncope. Groups of patients with so-called cardiodepressive vasovagal syncope (VVS_2) during HUTT and patients who did not faint during the test were compared. Two types of HUT tests were analyzed: with spontaneous (SB) or controlled breathing (CB). In our study, SampEn was higher in VVS_2 patients during SB, and PermEn was higher in VVS_2 patients during CB. Irrespective of the type of breathing during the test, SampEn and PermEn were similar in patients with the same type of reaction during HUTT. The use of several entropy-based parameters seems to be useful in HRV assessment in patients with vasovagal fainting.