Malignant melanoma is characterized by growing incidence, early metastasis, and a lack of effective treatment for advanced disease, suggesting a pressing need for novel therapeutic approaches. Conditionally replicative adenoviruses (CRAds) constitute a new and promising strategy for cancer treatment that has been rapidly translated into clinical trials. We engineered novel melanoma-targeted CRAds, AdTyrdelta24 and AdTyrdelta2delta24, by replacing the adenoviral E1A promoter with a cassette containing a polyA sequence and a human tyrosinase enhancer/promoter construct (hTyr2E/P). The small size of this cassette allows retention of the E3 region within these CRAds, which was shown to enhance viral spread and oncolysis. In addition, we introduced mutations (delta24 and delta2delta24) into the viral E1A gene, which attenuate adenoviral replication in quiescent cells. The cell cycle pathways mediating this attenuation are defective in melanoma cells. By analysis of E1A expression, we prove fidelity of hTyr2E/P in the adenoviral genome and in the context of viral replication when an upstream polyA was included. We further show efficient cytotoxicity of AdTyrdelta24 and AdTyrdelta2delta24 in melanoma cell lines and a 100-1000-fold attenuation in cell lines derived from various nonmelanocytic tissues. Virus replication and progeny production of these viruses were similarly selective, resulting in 200-800-fold higher virus yields in melanoma cells versus control cells, thus establishing viral cytolysis and spread as the cause of the observed cell killing. Cytotoxicity of AdTyrdelta24 for normal fibroblasts and keratinocytes was strongly attenuated, and this virus caused selective killing of melanoma cells but not surrounding keratinocytes in a coculture system. Progeny production and cytotoxicity of AdTyrdelta24 in melanoma cells were similar to matching viruses containing the stronger cytomegalovirus enhancer/promoter instead of hTyr2E/P. Furthermore, AdTyrdelta24 showed a cytopathic effect similar to the wild-type E1A containing AdTyrwt and only minimally reduced compared with wild-type adenovirus. We conclude that the generated CRAds AdTyrdelta24 and AdTyrdelta2delta24 constitute novel targeted agents for gene therapy and viral oncolysis of metastatic melanoma.