Complexity analysis of short-term cardiovascular control is traditionally performed using entropy-based approaches including corrective terms or strategies to cope with the loss of reliability of conditional distributions with pattern length. This study proposes a new approach aiming at the estimation of conditional entropy (CE) from short data segments (about 250 samples) based on the k-nearest-neighbor technique. The main advantages are: (i) the control of the loss of reliability of the conditional distributions with the pattern length without introducing a priori information; (ii) the assessment of complexity indexes without fixing the pattern length to an arbitrary low value. The approach, referred to as k-nearest-neighbor conditional entropy (KNNCE), was contrasted with corrected approximate entropy (CApEn), sample entropy (SampEn) and corrected CE (CCE), being the most frequently exploited approaches for entropy-based complexity analysis of short cardiovascular series. Complexity indexes were evaluated during the selective pharmacological blockade of the vagal and/or sympathetic branches of the autonomic nervous system. We found that KNNCE was more powerful than CCE in detecting the decrease of complexity of heart period variability imposed by double autonomic blockade. In addition, KNNCE provides indexes indistinguishable from those derived from CApEn and SampEn. Since this result was obtained without using strategies to correct the CE estimate and without fixing the embedding dimension to an arbitrary low value, KNNCE is potentially more valuable than CCE, CApEn and SampEn when the number of past samples most useful to reduce the uncertainty of future behaviors is high and/or variable among conditions and/or groups.