Recently, adenovirus (Ad) has been utilized as a viral vector for efficient gene delivery. However, substantial immunogenicity and toxicity have obstructed oncolytic Ad's transition into clinical studies. The goal of this study is to generate an adenoviral vector complexed with multidegradable bioreducible core-cross-linked polyethylenimine (rPEI) polymer that has low immunogenicity and toxicity while having higher transduction efficacy and stability. We have synthesized different molecular weight rPEIs and complexed with Ad at varying molar ratios to optimize delivery of the Ad/polymer complex. The size and surface charge of Ad/rPEIs were characterized. Of note, Ad/rPEIs showed significantly enhanced transduction efficiency compared to either naked Ad or Ad/25 kDa PEI in both coxsackievirus and adenovirus receptor (CAR) positive and negative cancer cells. The cellular uptake result demonstrated that the relatively small size of Ad/16 kDa rPEIs (below 200 nm) was more critical to the complex's internalization than its surface charge. Cancer cell killing effect and viral production were significantly increased when oncolytic Ad (RdB/shMet, or oAd) was complexed with 16 kDa rPEI in comparison to naked oAd-, oAd/25 kDa PEI-, or oAd/32 kDa rPEI-treated cells. This increased anticancer cytotoxicity was more readily apparent in CAR-negative MCF7 cells, implying that it can be used to treat a broad range of cancer cells. Furthermore, A549 and HT1080 cancer cells treated with oAd/16 kDa rPEI had significantly decreased Met and VEGF expression compared to either naked oAd or oAd/25 kDa PEI. Overall, these results demonstrate that shMet expressing oncolytic Ad complexed with multidegradable bioreducible core-cross-linked PEI could be used as efficient and safe cancer gene therapy.