Adenoviruses (Ads), especially HAdV-5, have been genetically equipped with tumor-restricted replication potential to enable applications in oncolytic cancer therapy. Such oncolytic adenoviruses have been well tolerated in cancer patients, but their anti-tumor efficacy needs to be enhanced. In this regard, it should be considered that cancer cells, dependent on their tissue of origin, can differ substantially from the normal host cells to which Ads are adapted by complex virus-host interactions. Consequently, viral replication efficiency, a key determinant of oncolytic activity, might be suboptimal in cancer cells. Therefore, we have analyzed both the replication kinetics of HAdV-5 and the virus-induced transcriptome in human bronchial epithelial cells (HBEC) in comparison to cancer cells. This is the first report on genome-wide expression profiling of Ads in their native host cells. We found that E1A expression and onset of viral genome replication are most rapid in HBEC and considerably delayed in melanoma cells. In squamous cell lung carcinoma cells, we observed intermediate HAdV-5 replication kinetics. Infectious particle production, viral spread and lytic activity of HAdV-5 were attenuated in melanoma cells versus HBEC. Expression profiling at the onset of viral genome replication revealed that HAdV-5 induced the strongest changes in the cellular transcriptome in HBEC, followed by lung cancer and melanoma cells. We identified prominent regulation of genes involved in cell cycle and DNA metabolism, replication and packaging in HBEC, which is in accord with the necessity to induce S phase for viral replication. Strikingly, in melanoma cells HAdV-5 triggered opposing regulation of said genes and, in contrast to lung cancer cells, no weak S phase induction was detected when using the E2F promoter as reporter. Our results provide a rationale for improving oncolytic adenoviruses either by adaptation of viral infection to target tumor cells or by modulating tumor cell functions to better support viral replication.