Background: Metastatic cancers with uncertain primary sites account for a significant portion of new cases. Among them, 3-9% are eventually assigned to cancer of unknown primary (CUP) site after a comprehensive diagnostic workup. Accurate identification of the primary site is the starting point for cancer diagnosis worldwide, and it is critical to guide the subsequent treatments of metastatic cancers. Here we presented a new DNA methylation sequencing-based method to predict the tissues of origin for metastatic cancers, including CUP. Methods: Cancer diagnosis relies substantially on histological and immunohistochemical analyses of formalin-fixed paraffin-embedded (FFPE) tissues. To take advantage of sample accessibility, we developed an optimized and streamlined method that was particularly used to generate reduced represent bisulfite sequencing (RRBS) libraries for genome-wide DNA methylation profiling with degraded DNA fragments. After confirming that data quality generated using the new FFPE-RRBS method was comparable with regular RRBS, we created an RRBS database using 541 fresh frozen samples across ten most common cancer types and 58 tumor-adjacent normal tissues. By incorporating four distinct methylation summary scores and seven machine learning approaches, 28 models were trained and compared for multi-class classification using our database. Lastly, we selected the best classifier to predict the tissues of origin utilizing 249 FFPE samples across ten metastatic cancer types and 12 FFPE samples from CUP patients. Meanwhile, the classifier was also cross-validated using a DNA methylation microarray data set of 4702 patients diagnosed with corresponding primary cancers in the TCGA project. Results: FFPE-RRBS allowed to construct decent libraries with heavily degraded genomic DNA within 20 hours. Comparable DNA methylation metrics were obtained for the RRBS libraries of paired primary cancer tissues (fresh frozen vs. FFPE) and the libraries of paired FFPE samples derived from primary and metastatic tissues. Among the 28 methylation-based classifiers, the mean methylation-based LinearSVC model performed the best, achieving an overall accuracy of 81% with an AUC of 0.95 in determining the primary sites of 10 metastatic cancers. In a cross-validation assay using the TCGA data set of 4702 cancer patients, the overall prediction accuracy and AUC were 92% and 0.99, respectively. Lastly, our model successfully identified the tissues of origin in 10 of 12 CUP patients in a prospective study. Conclusions: The FFPE-RRBS is a novel method for efficient profiling of heavily degraded FFPE samples and the mean methylation-based LinearSVC model can predict the tissues of origin for metastatic cancers and CUP with high accuracy.