Elevated, tumor-derived extracellular vesicle (tdEV) and circulating tumor cell (CTC) loads in metastatic cancer are associated with poor clinical outcome. Herein, we investigate whether endothelium-derived extracellular vesicles (edEVs) can be detected in the blood of metastatic colorectal cancer (mCRC) patients, and whether those vesicles associate with prognosis. The open-source ACCEPT (Automated CTC Classification, Enumeration, and Phenotyping) software was used to enumerate edEVs, tdEVs, and other objects from digitally stored CellSearch images acquired after CTC and circulating endothelial cell (CEC) enrichment from the blood of 395 mCRC patients before the initiation of a new therapy. Patients had participated in the prospective phase III CAIRO2 study. The presence of edEVs was found 5- to 10-fold higher than CECs. The hazard ratio (HR) (95% CI) of progression-free survival (PFS) for increased CTCs (≥3 in 7.5 mL), tdEVs (≥40 in 7.5 mL), and edEVs (≥287 in 4.0 mL.) was 1.4 (1.1–1.9), 2.0 (1.5–2.6), and 1.7 (1.2–2.5), respectively. The HR of Overall Survival (OS) for increased CTCs, tdEVs and edEVs was 2.2 (1.7–3.0), 2.7 (2.0–3.5), and 2.1 (1.5–2.8), respectively. There was no cut-off value for CECs, leading to a dichotomization of patients with a significant HR. Only tdEVs remained a significant predictor of OS in the final multivariable model.