Viruses use cellular machinery to enter and infect cells. In this study we address the cell entry mechanisms of nonenveloped adenoviruses (Ads). We show that protein VI, an internal capsid protein, is rapidly exposed after cell surface attachment and internalization and remains partially associated with the capsid during intracellular transport. We found that a PPxY motif within protein VI recruits Nedd4 E3 ubiquitin ligases to bind and ubiquitylate protein VI. We further show that this PPxY motif is involved in rapid, microtubule-dependent intracellular movement of protein VI. Ads with a mutated PPxY motif can efficiently escape endosomes but are defective in microtubule-dependent trafficking toward the nucleus. Likewise, depletion of Nedd4 ligases attenuates nuclear accumulation of incoming Ad particles and infection. Our data provide the first evidence that virus-encoded PPxY motifs are required during virus entry, which may be of significance for several other pathogens.