Objectives: To explore the effects of preoperative high-intensity interval training (HIIT) compared to usual care on tumour natural killer (NK)-cell infiltration in men with localised prostate cancer (PCa), as NK-cell infiltration has been proposed as one of the key mechanisms whereby exercise can modulate human tumours. Patients and Methods: A total of 30 patients with localised PCa undergoing radical prostatectomy (RP) were randomised (2:1) to either preoperative aerobic HIIT four-times weekly (EX; n = 20) or usual care (CON; n = 10) from time of inclusion until scheduled surgery. Tumour NK-cell infiltration was assessed by immunohistochemistry (CD56⁺) in diagnostic core needle biopsies and corresponding prostatic tissue from the RP. Changes in cardiorespiratory fitness, body composition, blood biochemistry, and health-related quality of life were also evaluated. Results: The change in tumour NK-cell infiltration did not differ between the EX and CON groups (between-group difference: −0.09 cells/mm², 95% confidence interval [CI] –1.85 to 1.66; P = 0.913) in the intention-to-treat analysis. The total number of exercise sessions varied considerably from four to 30 sessions. The per-protocol analysis showed a significant increase in tumour NK-cell infiltration of 1.60 cells/mm² (95% CI 0.59 to 2.62; P = 0.004) in the EX group. Further, the total number of training sessions was positively correlated with the change in NK-cell infiltration (r = 0.526, P = 0.021), peak oxygen uptake (r = 0.514, P = 0.035) and peak power output (r = 0.506, P = 0.038). Conclusion: Preoperative HIIT did not result in between-group differences in tumour NK-cell infiltration. Per-protocol and exploratory analyses demonstrate an enhanced NK-cell infiltration in PCa. Future studies are needed to test the capability of exercise to increase tumour immune cell infiltration.