A cardiorespiratory-based automatic sleep staging system for subjects with sleep-disordered breathing is described. A simplified three-state system is used: Wakefulness (W), rapid eye movement (REM) sleep (R), and non-REM sleep (S). The system scores the sleep stages in standard 30-s epochs. A number of features associated with the epoch RR-intervals, an inductance plethysmography estimate of rib cage respiratory effort, and an electrocardiogram-derived respiration (EDR) signal were investigated. A subject-specific quadratic discriminant classifier was trained, randomly choosing 20% of the subject's epochs (in appropriate proportions of W, S and R) as the training data. The remaining 80% of epochs were presented to the classifier for testing. An estimated classification accuracy of 79% (Cohen's kappa value of 0.56) was achieved. When a similar subject-independent classifier was trained, using epochs from all other subjects as the training data, a drop in classification accuracy to 67% (kappa = 0.32) was observed. The subjects were further broken in groups of low apnoea-hypopnea index (AHI) and high AHI and the experiments repeated. The subject-specific classifier performed better on subjects with low AHI than high AHI; the performance of the subject-independent classifier is not correlated with AHI. For comparison an electroencephalograms (EEGs)-based classifier was trained utilizing several standard EEG features. The subject-specific classifier yielded an accuracy of 87% (kappa = 0.75), and an accuracy of 84% (kappa = 0.68) was obtained for the subject-independent classifier, indicating that EEG features are quite robust across subjects. We conclude that the cardiorespiratory signals provide moderate sleep-staging accuracy, however, features exhibit significant subject dependence which presents potential limits to the use of these signals in a general subject-independent sleep staging system.