Purpose: Pheochromocytoma and paraganglioma (PPGL) are rare neuroendocrine tumors, associated with highly variable postoperative evolution. The scarcity of reliable PPGL prognostic markers continues to complicate patient management. In this study, we explored genome-wide DNA methylation patterns in the context of PPGL malignancy to identify novel prognostic markers. Experimental Design: We retrospectively investigated DNA methylation patterns in PPGL with and without metastases using high-throughput DNA methylation profiling data (Illumina 27K) from two large, well-characterized discovery (n = 123; 24 metastatic) and primary validation (n = 154; 24 metastatic) series. Additional validation of candidate CpGs was performed by bisulfite pyrosequencing in a second independent set of 33 paraffin-embedded PPGLs (19 metastatic). Results: Of the initial 86 candidate CpGs, we successfully replicated 52 (47 genes), associated with metastatic PPGL. Of these, 48 CpGs showed significant associations with time to progression even after correcting for SDHB genotype, suggesting their value as prognostic markers independent of genetic background. Hypermethylation of RDBP (negative elongation factor complex member E) in metastatic tumors was further validated by bisulfite pyrosequencing [Db_{metastatic-benign} = 0.29, P = 0.003; HR, 1.4; 95% confidence interval (CI), 1.1-2.0; P = 0.018] and may alter transcriptional networks involving (RERG, GPX3, and PDZK1) apoptosis, invasion, and maintenance of DNA integrity. Conclusions: This is the first large-scale study of DNA methylation in metastatic PPGL that identifies and validates prognostic markers, which could be used for stratifying patients according to risk of developing metastasis. Of the three CpGs selected for further validation, one (RDBP) was clearly confirmed and could be used for stratifying patients according to the risk of developing metastases.