We demonstrate that prostate cancer can be identified by flow cytometric profiling of blood immune cell subsets. Herein, we profiled natural killer (NK) cell subsets in the blood of 72 asymptomatic men with Prostate-Specific Antigen (PSA) levels < 20 ng ml^-1, of whom 31 had benign disease (no cancer) and 41 had prostate cancer. Statistical and computational methods identified a panel of eight phenotypic features (C⁢D⁢56d⁢i⁢m⁢C⁢D⁢16h⁢i⁢g⁢h, C⁢D⁢56+⁢D⁢N⁢A⁢M-1-, C⁢D⁢56+⁢L⁢A⁢I⁢R-1+, C⁢D⁢56+⁢L⁢A⁢I⁢R-1-, C⁢D⁢56b⁢r⁢i⁢g⁢h⁢t⁢C⁢D⁢8+, C⁢D⁢56+⁢N⁢K⁢p⁢30+, C⁢D⁢56+⁢N⁢K⁢p⁢30-, C⁢D⁢56+⁢N⁢K⁢p⁢46+) that, when incorporated into an Ensemble machine learning prediction model, distinguished between the presence of benign prostate disease and prostate cancer. The machine learning model was then adapted to predict the D’Amico Risk Classification using data from 54 patients with prostate cancer and was shown to accurately differentiate between the presence of low-/intermediate-risk disease and high-risk disease without the need for additional clinical data. This simple blood test has the potential to transform prostate cancer diagnostics.