Background: The immune system plays a vital role in cancer development and progression. Strategies mobilizing cytotoxic cells of the immune system to combat immunosuppression in cancer may help to improve the treatment response of patients. To this end, we aimed to characterize the anti-cancer effect of acute exercise, including the involvement of inflammatory signals. Patients and methods: Twenty patients with early-stage prostate cancer (PCa) scheduled to undergo prostatectomy performed one bout of acute exercise consisting of a watt-max test and four high-intensity intervals. Natural Killer (NK), NKT-like and T cell phenotype, NK cell cytotoxic activity (NKCA), and NKCA per-cell against cell lines of leukemia (K562) and prostate cancer origin (LNCaP and PC-3) were assessed. Inflammatory markers (TNF-α, IL-6, and CRP) were measured in plasma. Results: Exercise increased NK, NKT-like, and CD8 T cell concentration in the circulation. Furthermore, exercise shifted immune cells towards a mature and cytotoxic phenotype e.g., NK cells exhibited higher CD57 as well as lower NKG2A expression. NKT-like and CD8 cells exhibited elevated CD57, TIGIT and Granzyme-B expression. Exercise significantly improved NKCA against K562 (+16% [5%; 27%]; p = 0.002) and LNCaP (+24% [14%; 34%]; p < 0.001) but not PC-3. NKCA per NK cell decreased during exercise and increased 1-h post exercise compared to baseline in K562, LNCap, and PC-3 cell lines. Baseline IL-6 correlated with lymphocyte, monocyte and T cell concentration pre-exercise and inversely correlated with the fold-change of mobilized lymphocytes and CD8 T cells during exercise. Furthermore, baseline IL-6 and TNF-α inversely correlated with NKCA against PC-3 cells during exercise. Conclusions: Acute exercise mobilized cytotoxic immune cells and improved NKCA in patients with PCa whereas low-grade inflammation might impair the response. Whether the observed improvements impact long-term outcomes warrant further investigation. Clinical trial number: NCT03675529.