Identifying the primary site of metastatic cancer is critical to guiding the subsequent treatment. Approximately 3-9% of metastatic patients are diagnosed with cancer of unknown primary sites (CUP) even after a comprehensive diagnostic workup. However, a widely accepted molecular test is still not available. Here, we report a method that applies formalin-fixed, paraffin-embedded tissues to construct reduced representation bisulfite sequencing libraries (FFPE-RRBS). We then generate and systematically evaluate 28 molecular classifiers, built on four DNA methylation scoring methods and seven machine learning approaches, using the RRBS library dataset of 498 fresh-frozen tumor tissues from primary cancer patients. Among these classifiers, the beta value-based linear support vector (BELIVE) performs the best, achieving overall accuracies of 81-93% for identifying the primary sites in 215 metastatic patients using top-k predictions (k = 1, 2, 3). Coincidentally, BELIVE also successfully predicts the tissue of origin in 81-93% of CUP patients (n = 68).