In obstructive sleep apnea, patients' sleep is fragmented leading to excessive daytime sleepiness and co-morbidities like arterial hypertension. However, traditional metrics are not always directly correlated with daytime sleepiness, and the association between traditional sleep quality metrics like sleep duration and arterial hypertension is still ambiguous. In a development cohort, we analysed hypnograms from mild (n = 213), moderate (n = 235) and severe (n = 277) obstructive sleep apnea patients as well as healthy controls (n = 105) from the European Sleep Apnea Database. We assessed sleep by the analysis of two-step transitions depending on obstructive sleep apnea severity and anthropometric factors. Two-step transition patterns were examined for an association to arterial hypertension or daytime sleepiness. We also tested cumulative distributions of wake as well as sleep-states for power-laws (exponent α) and exponential distributions (decay time τ) in dependency on obstructive sleep apnea severity and potential confounders. Independent of obstructive sleep apnea severity and potential confounders, wake-state durations followed a power-law distribution, while sleep-state durations were characterized by an exponential distribution. Sleep-stage transitions are influenced by obstructive sleep apnea severity, age and gender. N2 → N3 → wake transitions were associated with high diastolic blood pressure. We observed higher frequencies of alternating (symmetric) patterns (e.g. N2 → N1 → N2, N2 → wake → N2) in sleepy patients both in the development cohort and in a validation cohort (n = 425). In conclusion, effects of obstructive sleep apnea severity and potential confounders on sleep architecture are small, but transition patterns still link sleep fragmentation directly to obstructive sleep apnea-related clinical outcomes like arterial hypertension and daytime sleepiness.