We introduce a sleep apnea characterization and classification approach based on a Heart Rate Variability (HRV) feature selection process, thus focusing on the characterization of the underlying process from a cardiac rate point of view. Therefore, we introduce linear and nonlinear variables, namely Cepstrum Coefficients (CC), Filterbanks (Fbank) and Detrended Fluctuation Analysis (DFA). Logistic Regression, Linear Discriminant Analysis and Quadratic Discriminant Analysis were used for classification purposes. The experiments were carried out using two databases. We achieved a per-segment accuracy of 84.76% (sensitivity = 81.45%, specificity = 86.82%, AUC = 0.92) in the Apnea-ECG Physionet database, whereas in the HuGCDN2014 database, provided by the Dr. Negrin University Hospital (Las Palmas de Gran Canaria, Spain), the best results were: accuracy = 81.96%, sensitivity = 70.95%, specificity = 85.47%, AUC = 0.87. The former results were comparable or better than those obtained by other methods for the same database in the recent literature. We have concluded that the selected features that best characterize the underlying process are common to both databases. This supports the fact that the conclusions reached are potentially generalizable. The best results were obtained when the three kinds of features were jointly used. Another notable fact is the small number of features needed to describe the phenomenon. Results suggest that the two first Fbanks, the first CC and the first DFA coefficient are the variables that best describe the RR pattern in OSA and, therefore, are especially relevant to extract discriminative information for apnea screening purposes.