Replicating adenovirus (Ad) vectors with tumour tissue specificity hold great promise for treatment of cancer. We have recently constructed a conditionally replicating Ad5 AdDeltaEP-TETP inducing tumour regression in a xenograft mouse model. For further improvement of this vector, we introduced four genetic modifications and analysed the viral cytotoxicity in a large panel of melanoma cell lines and patient-derived melanoma cells. (1) The antiapoptotic gene E1B-19 kDa (Delta19 mutant) was deleted increasing the cytolytic activity in 18 of 21 melanoma cells. (2) Introduction of the E1A 122-129 deletion (Delta24 mutant), suggested to attenuate viral replication in cell cycle-arrested cells, did not abrogate this activity and increased the cytolytic activity in two of 21 melanoma cells. (3) We inserted an RGD sequence into the fiber to extend viral tropism to alphav integrin-expressing cells, and (4) swapped the fiber with the Ad35 fiber (F35) enhancing the tropism to malignant melanoma cells expressing CD46. The RGD-fiber modification strongly increased cytolysis in all of the 11 CAR-low melanoma cells. The F35 fiber-chimeric vector boosted the cytotoxicity in nine of 11 cells. Our results show that rational engineering additively enhances the cytolytic potential of Ad vectors, a prerequisite for the development of patient-customized viral therapies.