Background: Improving early cancer detection has the potential to significantly reduce cancer-related mortality. Cell-free methylated DNA immunoprecipitation and high-throughput sequencing (cfMedDIP-seq) is a highly sensitive, low-input, cost-efficient and bisulfite-free assay capable of detecting and classifying various tumor types. We tested the feasibility of cfMeDIP-seq to detect RCC in plasma samples and, for the first time, in urine cell-free DNA (cfDNA), with an emphasis on early-stage disease. Methods: We performed cfMeDIP-seq on 117 samples (72 plasma and 45 urine samples): 68 stage I-IV RCC cases pre-nephrectomy, 21 stage IV urothelial bladder cancer (UBC) plasma samples from 15 patients, and 28 healthy cancer-free controls. 60.5% of plasma samples and 66.7% of urine samples came from patients with TNM Stage I/II disease. cfDNA was immunoprecipitated and enriched using an antibody targeting 5-methylcytosine and amplified to create a sequence-ready library. The top differentially methylated regions (DMRs) which partitioned RCC and control samples or UBC were used to train a regularized binomial generalized linear model using 80% of the samples as a training set. The 20% of withheld test samples were then assigned a probability of being RCC or control. This process was repeated 100 times. This was performed using both plasma and urine cfDNA samples. Results: We identified 89,799 DMRs in plasma samples and 38,462 DMRs in urine samples. Iterative training and classification of held out samples, using the 300 DMRs which partitioned RCC and control samples, resulted in a mean AUROC of 0.990 (95% CI 0.984-0.997) in plasma samples and 0.791 (95% CI 0.759-0.823) in urine samples. Classification performance between tumor types was evaluated comparing plasma cfDNA from patients with RCC and UBC, resulting in a mean AUROC of 0.954 (95% CI 0.940-0.969). Conclusions: cfMeDIP-seq is a powerful tool for genome-wide discovery of non-invasive DNA methylation biomarkers. This is the first independent validation of plasma cfMeDIP-seq, demonstrating near-perfect classification of RCC in a cohort enriched for patients with early-stage disease and the potential of urine cfDNA methylome-based biomarkers for cancer detection.