The nonlinear analysis of biological time series provides new possibilities to improve computer aided diagnostic systems, traditionally based on linear techniques. The cardiotocography (CTG) examination records simultaneously the fetal heart rate (FHR) and the maternal uterine contractions. This paper shows, at first, that both signals present nonlinear components based on the surrogate data analysis technique and exploratory data analysis with the return (lag) plot. After that, a nonlinear complexity analysis is proposed considering two databases, intrapartum (CTG-I) and antepartum (CTG-A) with previously identified normal and suspicious/pathological groups. Approximate Entropy (ApEn) and Sample Entropy (SampEn), which are signal complexity measures, are calculated. The results show that low entropy values are found when the whole examination is considered, ApEn = 0.3244 ± 0.1078 and SampEn = 0.2351 ± 0.0758 (average ± standard deviation). Besides, no significant difference was found between the normal (ApEn = 0.3366 ± 0.1250 and SampEn = 0.2532 ± 0.0818) and suspicious/pathological (ApEn = 0.3420 ± 0.1220 and SampEn = 0.2457 ± 0.0850) groups for the CTG-A database. For a better analysis, this work proposes a windowed entropy calculation considering 5-min window. The windowed entropies presented higher average values (ApEn = 0.6505 ± 0.2301 and SampEn = 0.5290 ± 0.1188) for the CTG-A and (ApEn = 0.5611 ± 0.1970 and SampEn = 0.4909 ± 0.1782) for the CTG-I. The changes during specific long-term events show that entropy can be considered as a first-level indicator for strong FHR decelerations (ApEn = 0.1487 ± 0.0341 and SampEn = 0.1289 ± 0.0301), FHR accelerations (ApEn = 0.1830 ± 0.1078 and SampEn = 0.1501 ± 0.0703) and also for pathological behavior such as sinusoidal FHR (ApEn = 0.1808 ± 0.0445 and SampEn = 0.1621 ± 0.0381).