Prostate cancer (PCa) immunotherapy has shown limited efficacy so far, even in advanced-stage cancers. The success rate of PCa immunotherapy might be improved by approaches more adapted to the immunobiology of the disease. The objective of this study was to perform a multi-omics analysis to identify immune genes associated with PCa progression to better characterize PCa immunobiology and propose new immunotherapeutic targets. mRNA, miRNA, methylation, copy number aberration, and single nucleotide variant datasets from The Cancer Genome Atlas PRAD cohort were analyzed after filtering for genes associated with immunity. Sparse partial least squares-discriminant analyses were performed to identify features associated with biochemical recurrence (BCR) in each type of omics data. Selected features predicted BCR with a balanced error rate (BER) of 0.20 to 0.51 in single-omics and of 0.05 in multi-omics analyses. Amongst features associated with BCR were genes from the Immunoglobulin Ig-like Receptor (LILR) family which are immune checkpoints with immunotherapeutic potential. Using Multivariate INTegrative (MINT) analysis, the association of five LILR genes with BCR was quantified in a combination of three RNA-seq datasets and confirmed with Kaplan-Meier analysis in both these and in an independent RNA-seq dataset. Finally, immunohistochemistry showed that a high number of LILRB1 positive cells within the tumors predicted long-term adverse outcomes. Thus, tumors characterized by abnormal expression of LILR genes have an elevated risk of recurring after definitive local therapy. The immunotherapeutic potential of these regulators to stimulate the immune response against PCa should be evaluated in pre-clinical models.