In this paper, we investigate the use of heart rate variability (HRV) for automatic newborn seizure detection. The proposed method consists of a sequence of processing steps, namely, obtaining HRV from the ECG, extracting a discriminating HRV feature set, selecting an optimal subset from the full feature set, and, finally, classifying the HRV into seizure/nonseizure using a supervised statistical classifier. Due to the fact that HRV signals are nonstationary, a set of time-frequency features from the newborn HRV is proposed and extracted. In order to achieve efficient HRV-based automatic newborn seizure detection, a two-phase wrapper-based feature selection technique is used to select the feature subset with minimum redundancy and maximum class discriminability. Tested on ECG recordings obtained from eight newborns with identified EEG seizure, the proposed HRV-based neonatal seizure detection algorithm achieved 85.7% sensitivity and 84.6% specificity. These results suggest that the HRV is sensitive to changes in the cardioregulatory system induced by the seizure, and therefore, can be used as a basis for an automatic seizure detection.