Autonomic cardiorespiratory activity changes across sleep stages. However, it is unknown to what extent it is affected by between- and within-subject variability during sleep. As it is hypothesized that the variability is caused by differences in subject demographics (age, gender, and body mass index), time, and physiology, we quantified these effects and investigated how they limit reliable cardiorespiratory-based sleep staging. Six representative parameters obtained from 165 overnight heartbeat and respiration recordings were analyzed. Multilevel models were used to evaluate the effects evoked by differences in sleep stages, demographics, time, and physiology between and within subjects. Results show that the between- and within-subject effects were found to be significant for each parameter. When adjusted by sleep stages, the effects in physiology between and within subjects explained more than 80% of total variance but the time and demographic effects explained less. If these effects are corrected, profound improvements in sleep staging can be observed. These results indicate that the differences in subject demographics, time, and physiology present significant effects on cardiorespiratory activity during sleep. The primary effects come from the physiological variability between and within subjects, markedly limiting the sleep staging performance. Efforts to diminish these effects will be the main challenge.