Craniocervical instability (CCI) is increasingly recognized in hereditary disorders of connective tissue and in some patients following suboccipital decompression for Chiari malformation (CMI) or low-lying cerebellar tonsils (LLCT). CCI is characterized by severe headache and neck pain, cervical medullary syndrome, lower cranial nerve deficits, myelopathy, and radiological metrics, for which occipital cervical fusion (OCF) has been advocated. We conducted a retrospective analysis of patients with CCI and Ehlers-Danlos syndrome (EDS) to determine whether the surgical outcomes supported the criteria by which patients were selected for OCF. Fifty-three consecutive subjects diagnosed with EDS, who presented with severe head and neck pain, lower cranial nerve deficits, cervical medullary syndrome, myelopathy, and radiologic findings of CCI, underwent open reduction, stabilization, and OCF. Thirty-two of these patients underwent suboccipital decompression for obstruction of cerebral spinal fluid flow. Questionnaire data and clinical findings were abstracted by a research nurse. Follow-up questionnaires were administered at 5-28 months (mean 15.1). The study group demonstrated significant improvement in headache and neck pain (p < 0.001), decreased use of pain medication (p < 0.0001), and improved Karnofsky Performance Status score (p < 0.001). Statistically significant improvement was also demonstrated for nausea, syncope (p < 0.001), speech difficulties, concentration, vertigo, dizziness, numbness, arm weakness, and fatigue (p = 0.001). The mental fatigue score and orthostatic grading score were improved (p < 0.01). There was no difference in pain improvement between patients with CMI/LLCT and those without. This outcomes analysis of patients with disabling CCI in the setting of EDS demonstrated significant benefits of OCF. The results support the reasonableness of the selection criteria for OCF. We advocate for a multi-center, prospective clinical trial of OCF in this population.