A few years ago, reactivation of human endogenous retrovirus K (HERV-K) proviruses in melanoma was described. The expression of HERV-K proteins induces humoral immune responses. The aim of the present study was to elucidate the prognostic relevance of serological anti-HERV-K reactivity in melanoma patients. In a retrospective study, anti-HERV-K Gag and Env antibodies were detected in 51 of the 312 randomly selected and blinded sera from melanoma patients, but not in any of the 70 sera from healthy controls. Comparing serological HERV-K reactivity with established melanoma markers revealed a significant correlation (p = 0.018, Chi-square test) with the stage of disease classified according to the American Joint Committee on Cancer (AJCC). Anti-HERV-K reactivity was elevated in patients with acrolentiginous/mucosal/uveal melanoma (tumor subtypes developing at sun-protected sites) compared to patients with lentigo/nodular/superficial spreading melanoma (p = 0.011, Chi-square test). Patients with anti-HERV-K antibodies had a significantly decreased disease-specific overall survival (stage I–IV, p < 0.001; stage I–III, p = 0.005, log-rank test). Significantly, multivariate Cox regression analysis including prognostic markers in clinical use (e.g., AJCC stage, T-class, serum level of S100-beta) revealed serological HERV-K reactivity as an independent marker of reduced survival probability (p = 0.027) in melanoma patients with the early stages of the disease (AJCC I–III). This is the first report that the humoral anti-HERV-K immune response may provide additional prognostic information to that of established melanoma markers.