Complexity of heartbeat interval series is typically measured by entropy. Recent studies have found that sample entropy (SampEn) or fuzzy entropy (FuzzyEn) quantifies essentially the randomness, which may not be uniformly identical to complexity. Additionally, these entropy measures are heavily dependent on the predetermined parameters and confined to data length. Aiming at improving the robustness of complexity assessment for short-term RR interval series, this study developed a novel measure—distribution entropy (DistEn). The DistEn took full advantage of the inherent information underlying the vector-to-vector distances in the state space by probability density estimation. Performances of DistEn were examined by theoretical data and experimental short-term RR interval series. Results showed that DistEn correctly ranked the complexity of simulated chaotic series and Gaussian noise series. The DistEn had relatively lower sensitivity to the predetermined parameters and showed stability even for quantifying the complexity of extremely short series. Analysis further showed that the DistEn indicated the loss of complexity in both healthy aging and heart failure patients (both p < 0.01), whereas neither the SampEn nor the FuzzyEn achieved comparable results (all p ≥ 0.05). This study suggested that the DistEn would be a promising measure for prompt clinical examination of cardiovascular function.