It is well known that biomedical signals, such as heart rate variability (HRV), electrocardiogram (ECG), electroencephalogram (EEG), and voice, arise from complex nonlinear dynamical systems, as the cardiovascular, nervous, or phonatory ones. Information extracted from these signals provides insights regarding the status of the underlying physiology. Complexity measures are helpful to quantitatively describe nonlinear biomedical systems and to detect changes in their dynamics that can be associated with physiological or pathological events [1–5]. These measures on biomedical signals and images can be used in a wide field of applications as pathology detection, decision support systems, treatment monitoring, and temporal segmentation. They can also be used to characterize biomedical systems that gave rise to those images and time series. However, in practice, many challenges emerge when these complexity measures are applied, such as the influence of the noise, the quantization effects, the lengths of the available data, or the parameter tuning. Many of these issues are still unsolved [6–8]. How to cope with these difficulties and how to obtain tools that can be employed in clinical practice are the subjects of this special issue. It is focused not only on the application of existing complexity measures on biomedical signals and images but also on the development of new complexity measure algorithms. Some interesting complexity-based works are also associated with machine learning-based strategies, automatization in parameter setting, and applications in pattern recognition problems, as well as developments and applications of novel complexity estimators for multivariate, multiscale, or multimodal data [9, 10].