The evolutionary progression from primary to metastatic prostate cancer is largely uncharted, and the implications for liquid biopsy are unexplored. We infer detailed reconstructions of tumor phylogenies in ten prostate cancer patients with fatal disease, and investigate them in conjunction with histopathology and tumor DNA extracted from blood and cerebrospinal fluid. Substantial evolution occurs within the prostate, resulting in branching into multiple spatially intermixed lineages. One dominant lineage emerges that initiates and drives systemic metastasis, where polyclonal seeding between sites is common. Routes to metastasis differ between patients, and likely genetic drivers of metastasis distinguish the metastatic lineage from the lineage that remains confined to the prostate within each patient. Body fluids capture features of the dominant lineage, and subclonal expansions that occur in the metastatic phase are non-uniformly represented. Cerebrospinal fluid analysis reveals lineages not detected in blood-borne DNA, suggesting possible clinical utility.