Despite advances in prenatal health care, neonatal sepsis remains a major cause of neonatal mortality. Early diagnosis and adequate treatment are essential to reduce morbidity and mortality related to this disease. In this paper, we propose a new method to detect neonatal sepsis based on heart rate (HR) complexity measures (entropy and compression indices) that takes into consideration neonatal gestational age. First, the percentile curves were computed for all the complexity indices using data from 118 control neonates. Eight indices were computed: the sample entropy (SampEn) and three indices to quantify the multiscale entropy (MSE) curve - the sum, the slope, and the product of the previous two - and the compression ratio (CR), using the bzip2 compressor, as well as the same three indices but related to the multiscale compression (MSC) curve. Then, the corresponding percentile was estimated for 23 sepsis neonates. Results show a significant decrease in the entropy indices SampEn and MSEsum and in the MSCslope a day before the detection of sepsis by the clinicians. The indices CR and MSCsum increased before the antibiotic take. These results imply that sepsis causes a random, uncorrelated pattern on the HR signal. Future studies should include a bigger data set to calculate a compound index comprising information of other physiological signals. Clinical Relevance - Prompt and accurate diagnosis of neona-tal sepsis is essential for the successful clinical management of neonates and significantly reduce morbidity and mortality. Complexity measures applied to the HR time series appear to detect sepsis in neonates starting one day before the clinical detection.