Abstract CTL and NK cells recognize and eliminate cancer cells. However, immune evasion, down regulation of immune function by the tumor microenvironment, or resistance of cancer cells are a major problem. While CTL and NK cells are both important to eliminate cancer, most studies address them individually. In a new experimental human model, we analysed combined primary human CTL and NK cell cytotoxicity against the melanoma cell line SK-Mel-5. At high effector-to-target ratios, MART-1-specific CTL or NK cells eliminated SK-Mel-5 cells within 24 hours indicating that SK-Mel-5 cells are initially not resistant. However, at lower effector-to-target ratios, which resemble conditions of the immune contexture in human cancer, a significant number of SK-Mel-5 cells survived. Whereas CTL pre-exposure induced resistance in surviving SK-Mel-5 cells to subsequent CTL or NK cell cytotoxicity, NK cell pre-exposure induced resistance in surviving SK-Mel-5 cells to NK cells but not to MART-1 specific CTL. In contrast, there was even a slight enhancement of CTL cytotoxicity against SK-Mel-5 cells following NK cell pre-exposure. In all other combinations, resistance to subsequent cytotoxicity was higher, if melanoma cells were pre-exposed to larger numbers of CTL or NK cells. Increases in human leukocyte antigen class I expression correlated with resistance to NK cells, while reduction in MART-1 antigen expression correlated with reduced CTL cytotoxicity. CTL cytotoxicity was rescued beyond control levels by exogenous MART-1 antigen. This study quantifies the interdependence of CTL and NK cell cytotoxicity and may guide strategies for efficient CTL-NK cell anti-melanoma therapies. Key points summary Cytotoxic T lymphocytes (CTL) and natural killer (NK) cells eliminate cancer cells. CTL and NK work in parallel, but most studies address them individually. In a new human experimental model, antigen-specific CTL and NK cell cytotoxicity interdependence against melanoma is shown. Whereas high numbers of antigen-specific CTL and NK cells eliminate all melanoma cells, lower, more physiological numbers induce resistance, in case secondary CTL or NK cell exposure follow initial CTL cell exposure or if secondary NK cell exposure follows initial NK cell exposure; only if secondary CTL exposure follows initial NK cell exposure no resistance of melanoma but even a slight enhancement of cytotoxicity was observed. Alterations in HLA-I expression correlated with resistance to NK cells, while reduction in antigen expression correlated with reduced CTL cytotoxicity. CTL cytotoxicity was rescued beyond control levels by exogenous antigen. The results should help to better understand and optimize immune therapies against cancer. Graphical abstract