In this study we explored the changes in the variability and complexity of the electrocardiogram (ECG) of flight phobics (N = 61) and a matched non-phobic control group (N = 58) when they performed a paced breathing task and were exposed to flight related stimuli. Lower complexity/entropy values were expected in phobics as compared to controls. The phobic system complexity as well as the heart rate variability (HRV) were expected to be reduced by the exposure to fearful stimuli. The multiscale entropy (MSE) analysis revealed lower entropy values in phobics during paced breathing and exposure, and a complexity loss was observed in phobics during exposure to threatening situations. The expected HRV decreases were not found in this study. The discussion is focused on the distinction between variability and complexity measures of the cardiac output, and on the usefulness of the MSE analysis in the field of anxiety disorders.