The aim of this study is to characterize in resting-state conditions the cerebral blood flow velocity (CBFV) signals of fibromyalgia patients. The anterior and middle cerebral arteries of both hemispheres from 15 women with fibromyalgia and 15 healthy women were monitored using Transcranial Doppler (TCD) during a 5-minute eyes-closed resting period. Several signal processing methods based on time, information theory, frequency and time-frequency analyses were used in order to extract different features to characterize the CBFV signals in the different vessels. Main results indicated that, in comparison with control subjects, fibromyalgia patients showed a higher complexity of the envelope CBFV and a different distribution of the power spectral density. In addition, it has been observed that complexity and spectral features show correlations with clinical pain parameters and emotional factors. The characterization features were used in a lineal model to discriminate between fibromyalgia patients and healthy controls, providing a high accuracy. These findings indicate that CBFV signals, specifically their complexity and spectral characteristics, contain information that may be relevant for the assessment of fibromyalgia patients in resting-state conditions.