There is substantial evidence of immune system dysfunction in chronic fatigue syndrome/myalgic encephalomyelitis (CFS/ME) but little is understood of exercise training effects on lymphocyte function in this illness. This study investigated whether graded and intermittent exercise improved CD8+ lymphocyte activation and natural killer cell degranulation markers compared to no exercise. Twenty-four chronic fatigue syndrome (CFS) patients (50.2 ± 10 year) were randomized to graded exercise (GE), intermittent exercise (IE) or usual care (UC) groups; a control group (CTL) of 18 matched sedentary non-CFS/ME participants were included for immunological variable comparisons. Main outcome measures were pre- and postintervention expression of CD3+CD8+CD38+ and CD3−CD16+56+CD107a+ (LAMP-1) CD107b+ (LAMP-2) and aerobic exercise capacity. The postintervention percentage of NK cells expressing LAMP-1 and -2 was significantly higher in IE compared to UC, and higher in GE compared to UC and CTL. LAMP-1 and LAMP-2 expression (absolute numbers and percent positive) increased significantly pre-to-postintervention for both GE and IE. Preintervention, the absolute number of CD8+CD38+ cells was significantly lower in CTL compared to UC and IE. There were no significant pre- to postintervention changes in CD8+CD38+ expression for any group. Aerobic exercise capacity was significantly improved by GE and IE. Twelve weeks of GE and IE increased the expression of NK cell activation and degranulation markers, suggesting enhanced immunosurveillance. Low-intensity exercise may also reduce CD8+CD38+ expression, a marker of inflammation. Both GE and IE improved exercise capacity without worsening CFS/ME symptoms, and more robust trials of these exercise modalities are warranted.