It was previously shown that CEACAM1 on melanoma cells strongly predicts poor outcome. Here, we show a statistically significant increase of serum CEACAM1 in 64 active melanoma patients, as compared to 48 patients with no evidence of disease and 37 healthy donors. Among active patients, higher serum CEACAM1 correlated with LDH values and with decreased survival. Multivariate analysis with neutralization of LDH showed that increased serum CEACAM1 carries a hazard ratio of 2.40. In vitro, soluble CEACAM1 was derived from CEACAM1(+), but neither from CEACAM1(−) melanoma cells nor from CEACAM1(+) lymphocytes, and directly correlated with the number of CEACAM1(+) melanoma cells. Production of soluble CEACAM1 depended on intact de novo protein synthesis and secretion machineries, but not on metalloproteinase function. An unusually high percentage of CEACAM1(+) circulating NK and T lymphocytes was demonstrated in melanoma patients. CEACAM1 inhibited killing activity in functional assays. CEACAM1 expression could not be induced on lymphocytes by serum from patients with high CEACAM1 expression. Further, expression of other NK receptors was impaired, which collectively indicate on a general abnormality. In conclusion, the systemic dysregulation of CEACAM1 in melanoma patients further denotes the role of CEACAM1 in melanoma and may provide a basis for new tumor monitoring and prognostic platforms.