Increased dietary intake of Selenium (Se) has been suggested to lower prostate cancer mortality, but supplementation trials have produced conflicting results. Se is incorporated into 25 selenoproteins. The aim of this work was to assess whether risk of prostate cancer is affected by genetic variants in genes coding for selenoproteins, either alone or in combination with Se status. 248 cases and 492 controls from an EPIC-Heidelberg nested case-control study were subjected to two-stage genotyping with an initial screening phase in which 384 tagging-SNPs covering 72 Se-related genes were determined in 94 cases and 94 controls using the Illumina Goldengate methodology. This analysis was followed by a second phase in which genotyping for candidate SNPs identified in the first phase was carried out in the full study using Sequenom. Risk of high-grade or advanced stage prostate cancer was modified by interactions between serum markers of Se status and genotypes for rs9880056 in SELK, rs9605030 and rs9605031 in TXNRD2, and rs7310505 in TXNRD1. No significant effects of SNPs on prostate cancer risk were observed when grade or Se status was not taken into account. In conclusion, the risk of high-grade or advanced-stage prostate cancer is significantly altered by a combination of genotype for SNPs in selenoprotein genes and Se status. The findings contribute to explaining the biological effects of selenium intake and genetic factors in prostate cancer development and highlight potential roles of thioredoxin reductases and selenoprotein K in tumour progression.