Obstructive sleep apnea (OSA) can have long-term cardiovascular and metabolic effects. The identification of OSA-related impairments would provide diagnostic and prognostic value. Heart rate variability (HRV) as a measure of cardiac autonomic regulation is a promising candidate marker of OSA and OSA-related conditions. We took advantage of the Physionet Apnea-ECG database for two purposes. First, we performed time- and frequency-domain analysis of nocturnal HRV on each recording of this database to evaluate the cardiac autonomic regulation in patients with nighttime sleep breathing disorders. Second, we conducted a logistic regression analysis (backward stepwise) to identify the HRV indices able to predict the apnea-hypopnea index (AHI) categories (i.e., "Severe OSA", AHI >/= 30; "Moderate-Mild OSA", 5 >/= AHI < 30; and "Normal", AHI < 5). Compared to the "Normal", the "Severe OSA" group showed lower high-frequency power in normalized units (HFnu) and higher low-frequency power in normalized units (LFnu). The standard deviation of normal R-R intervals (SDNN) and the root mean square of successive R-R interval differences (RMSSD) were independently associated with sleep-disordered breathing. Our findings suggest altered cardiac autonomic regulation with a reduced parasympathetic component in OSA patients and suggest a role of nighttime HRV in the characterization and identification of sleep breathing disorders.