Although it has been known for 50 years that adenoviruses (Ads) interact with erythrocytes ex vivo, the molecular and structural basis for this interaction, which has been serendipitously exploited for diagnostic tests, is unknown. In this study, we characterized the interaction between erythrocytes and unrelated Ad serotypes, human 5 (HAd5) and 37 (HAd37), and canine 2 (CAV-2). While these serotypes agglutinate human erythrocytes, they use different receptors, have different tropisms and/or infect different species. Using molecular, biochemical, structural and transgenic animal-based analyses, we found that the primary erythrocyte interaction domain for HAd37 is its sialic acid binding site, while CAV-2 binding depends on at least three factors: electrostatic interactions, sialic acid binding and, unexpectedly, binding to the coxsackievirus and adenovirus receptor (CAR) on human erythrocytes. We show that the presence of CAR on erythrocytes leads to prolonged in vivo blood half-life and significantly reduced liver infection when a CAR-tropic Ad is injected intravenously. This study provides i) a molecular and structural rationale for Ad-erythrocyte interactions, ii) a basis to improve vector-mediated gene transfer and iii) a mechanism that may explain the biodistribution and pathogenic inconsistencies found between human and animal models.