Background: Immunodeficiencies are genetic diseases known to predispose an individual to cancer owing to defective immunity towards malignant cells. However, the link between immunodeficiency and prostate cancer progression remains unclear. Therefore, the aim of this study was to evaluate the effects of common genetic variants among eight immunodeficiency pathway-related genes on disease recurrence in prostate cancer patients treated with radical prostatectomy. Methods: Genetic and bioinformatic analyses on 19 haplotype-tagging single-nucleotide polymorphisms in eight immunodeficiency pathway-related genes were conducted in 458 patients with prostate cancer after receiving radical prostatectomy. Furthermore, the TNFRSF13B was knocked down in 22Rv1 and PC-3 human prostate cancer cell lines via transfecting short hairpin RNAs and cell proliferation and colony formation assays were performed. The molecular mechanisms underlying the effects of TNFRSF13B were further explored by microarray gene expression profiling. Results: TNFRSF13B rs4792800 was found to be significantly associated with biochemical recurrence even after adjustment for clinical predictors and false discovery rate correction (adjusted hazard ratio 1.78, 95% confidence interval 1.16–2.71, p = 0.008), and the G allele was associated with higher TNFRSF13B expression (p = 0.038). Increased TNFRSF13B expression suggested poor prognosis in four independent prostate cancer datasets. Furthermore, silencing TNFRSF13B expression resulted in decreased colony formation of 22Rv1 and PC-3 cells through modulating the cell cycle and p53 signalling pathways. Conclusions: The present study suggests the potential role of immunodeficiency pathway-related genes, primarily TNFRSF13B, in prostate cancer progression.