Chronic Fatigue Syndrome (CFS) and Fibromyalgia (FM) often co-occur as medically unexplained conditions linked to disrupted physiological regulation, including altered sleep. Building on the work of Kishi et al. [8], who identified differences in sleep-stage transitions in women with CFS and CFS+FM, we exploited the same strictly controlled clinical cohort using a Bayesian Network (BN) to quantify detailed patterns of sleep and its dynamics. Our BN confirmed that sleep transitions are best described as a second-order process [15], achieving a next-stage predictive accuracy of 70.6%, validated on two independent data sets with domain shifts (60.1–69.8% accuracy). Notably, we demonstrated that sleep dynamics can reveal the actual diagnoses. Our BN successfully differentiated healthy, CFS, and CFS+FM individuals, achieving an AUROC of 75.4%. Using interventions, we quantified sleep alterations attributable specifically to CFS and CFS+FM, identifying changes in stage prevalence, durations, and first- and second-order transitions. These findings reveal novel markers for CFS and CFS+FM in early-to-mid-adulthood women, offering insights into their physiological mechanisms and supporting their clinical differentiation.