Obstructive sleep apnea (OSA) is the most common manifestation of sleep-related breathing disorders that are often accompanied by dysfunction of the autonomic nervous system. The main objective of the study was to assess the usefulness of heart rate variability (HRV) analysis in the diagnosis of patients with severe OSA and in the assessment of the effects of 3-month treatment with continuous positive airway pressure (CPAP). There were 54 patients enrolled in the study. The OSA group consisted of 39 patients suffering from severe OSA (apnea/hypopnea index >30/h), and the control group included 15 non-OSA patients with matched demographic characteristics and comorbidities. All patients underwent 24-h Holter electrocardiographic monitoring. HRV was analyzed using the time- and frequency-domains. We found that OSA patients had decreases in time-domains and increases in frequency-domains of HRV, compared to non-OSA controls, which strongly suggested a clinically disadvantageous shift in the balance of parasympathetic/sympathetic activity toward the latter. Further, CPAP treatment, partly, albeit significantly, reversed the OSA-induced changes in HRV. We conclude that HRV analysis may be of help in the diagnosis of OSA and in the monitoring of the effectiveness of treatment.