Isolation of metastatic circulating tumor cells (CTCs) from cancer patients is of high value for disease monitoring and molecular characterization. Despite the development of many new CTC isolation platforms in the last decade, their isolation and detection has remained a challenge due to the lack of specific and sensitive markers. In this feasibility study, we present a method for CTC isolation based on the specific binding of the malaria rVAR2 protein to oncofetal chondroitin sulfate (ofCS). We show that rVAR2 efficiently captures CTCs from hepatic, lung, pancreatic, and prostate carcinoma patients with minimal contamination of peripheral blood mononuclear cells. Expression of ofCS is present on epithelial and mesenchymal cancer cells and is equally preserved during epithelial-mesenchymal transition of cancer cells. In 25 stage I-IV prostate cancer patient samples, CTC enumeration significantly correlates with disease stage. Lastly, rVAR2 targets a larger and more diverse population of CTCs compared to anti-EpCAM strategies.