Androgen receptor (AR) drives prostate cancer (PCa) development and progression. AR chromatin binding profiles are highly plastic and form recurrent programmatic changes that differentiate disease stages, subtypes and patient outcomes. While prior studies focused on concordance between patient subgroups, inter-tumor heterogeneity of AR enhancer selectivity remains unexplored. Here we report high levels of AR chromatin binding heterogeneity in human primary prostate tumors, that overlap with heterogeneity observed in healthy prostate epithelium. Such heterogeneity has functional consequences, as somatic mutations converge on commonly-shared AR sites in primary over metastatic tissues. In contrast, less-frequently shared AR sites associate strongly with AR-driven gene expression, while such heterogeneous AR enhancer usage also distinguishes patients' outcome. These findings indicate that epigenetic heterogeneity in primary disease is directly informative for risk of biochemical relapse. Cumulatively, our results illustrate a high level of AR enhancer heterogeneity in primary PCa driving differential expression and clinical impact.