Background: Early detection may reduce cancer mortality. Systematic screening programs are available only for a limited number of cancers (e.g., colorectal cancer). The majority of common cancers are detected after the onset of signs and symptoms, making treatment difficult or less effective. We describe here a multi-cancer epigenetic approach for simultaneous cancer detection of common cancers (̃70% of adult cancers) and determination of tissue of origin (TOO) using circulating cell-free DNA (cfDNA) from plasma. Methods: A total of 2241 cancer cases, including patients with newly diagnosed primary colorectal, gastric, esophageal, liver, lung, and breast cancer (stages I-III or equivalent) and 2289 non-cancer controls were recruited from participating hospitals in China. Study participants were randomly assigned into a training set (70%) and a testing set (30%), and patients were matched for cancer types and stages. Plasma samples were collected before radical treatment or surgery. The 5hmC-Seal, a highly sensitive chemical labeling technique, was used to profile genome-wide 5-hydroxymethylcytosines (5hmC) in cfDNA from ̃5mL of plasma per person, followed by the next-generation sequencing, data summarization at gene-level, and normalization. We applied the elastic net regularization to establish a predictive rule based on the multivariable logistic regression model for cancer detection in the training set as well as a multiclass classification model for determining TOO. The final solution for simultaneous cancer detection and TOO determination was established by integrating the 5hmC-based models and protein markers (e.g., AFP). Overall sensitivity and specificity were computed and reported in the testing set of 670 cancer cases and 686 non-cancer controls. Results: For the primary scenario (i.e., stages I-III or equivalent), at specificity of 95%, the overall sensitivity achieved 79.3% for detecting a cancer patient in all six cancer types in the testing set, except stage I lung cancer, for which the multi-cancer detection solution showed a sensitivity of 51%. Notably, for individuals with a negative result from conventional protein markers (e.g., AFP, CEA), the 5hmC-only models showed 67.6% sensitivity at 98.2% specificity in the testing set, representing significant improvement. In the testing set, among the 500 cancer patients who were detected from the multi-cancer detection solution, 435 patients were assigned a TOO; of those, 362 (83.2%) TOO were correctly determined. Conclusions: The 5hmC-Seal in cfDNA shows the potential as a non-invasive tool that could be integrated into a screening program for simultaneous detection of common cancers and TOO localization. This approach can be expanded to additional cancer types and is currently undergoing validation in prospectively recruited cohorts.