Multiple sclerosis (MS) is an inflammatory demyelinating disease of the central nervous system (CNS) with the majority of cases characterised by relapsing/remitting (RRMS) attacks of neurologic dysfunction followed by variable resolution. Improving clinical outcomes in RRMS requires both a better understanding of the immunological mechanisms driving recurrent demyelination and better means of predicting future disease course to facilitate early targeted therapy. Here, we apply hypothesis-generating network transcriptomics to CD8+ cells isolated from patients in RRMS, identifying a signature reflecting expansion of a subset of CD8+ natural killer cells (NK8+) associated with favourable outcome. NK8+ are capable of regulating CD4+ T cell activation and proliferation in vitro, with reduced expression of HLA-G binding inhibitory receptors and consequent reduced sensitivity to HLA-G-mediated suppression. We identify surrogate markers of the NK8+ signature in peripheral blood leucocytes and validate their association with clinical outcome in an independent cohort, suggesting their measurement may facilitate early, targeted therapy in RRMS.