Adenovirus (Ad) is used as a vector for gene delivery in therapies involving genetic disease, vascular disease, and cancer. The first step for efficient gene transfer is effective virus binding to the target cells. We have found that Ad-mediated gene delivery to multiple cell types is much less efficient compared to epithelial-derived cells. Low gene delivery to nonepithelial cell types was directly correlated to a deficiency of the cellular receptor which mediates Ad binding. To overcome this inefficiency we constructed a new virus, AdPK, that contains a heparin-binding domain that targets the virus to broadly expressed, heparan-containing cellular receptors. AdPK delivers genes to multiple cell types at markedly higher efficiencies than unmodified Ad. Viruses with enhanced attachment characteristics significantly improve gene transfer efficiency and may expand the tissues amenable to efficient Ad-mediated gene therapy.