Background: Tumor-derived soluble factors, including soluble HLA molecules, can contribute to cancer immune escape and therefore impact on clinical course of malignant diseases. We previously reported that melanoma cells produce, in vitro, soluble forms of the non-classical MHC class I molecule HLA-E (sHLA-E). In order to investigate sHLA-E production by various tumors and to address its potential value as a tumor-associated marker, we developed a specific ELISA for the quantification of sHLA-E in biological fluids. Methodology/Principal Findings: We developed a sHLA-E specific and sensitive ELISA and we showed that serum sHLA-E levels were significantly elevated (P,0.01) in melanoma patients (n = 127), compared with healthy donors (n = 94). sHLA-E was also detected in the culture supernatants of a wide variety of tumor cell lines (n = 98) including melanomas, kidney, colorectal and breast cancers. Cytokines regulation of sHLA-E production by tumor cells was also carried out. IFN-c, IFN-a and TNF-a were found to upregulate sHLA-E production by tumor cells. Conclusions/Significance: In view of the broad tumor tissue release of HLA-E and its up-regulation by inflammatory cytokines, sHLA-E should be studied for its involvement in immune responses against tumors. Interestingly, our results demonstrated a positive association between the presence of serum sHLA-E and melanoma. Therefore, the determination of sHLA-E levels, using ELISA approach, may be investigated as a clinical marker in cancer patients.