The binding of the adenovirus (Ad) protein E3-19K with the human leukocyte antigen (HLA) plays an important role in Ad infections, which is the causative agent of a series of gastrointestinal, respiratory and ocular diseases. The objective of this research is to evaluate the essential interactions between E3-19K and HLA-A2 using the X-ray crystal structure of the E3-19K/HLA-A2 complex, and to identify small molecules that could potentially disrupt their binding. Computational methods, including molecular dynamic simulations, MM/GBSA calculations, and computational solvent mapping, were implemented to determine potential binding site(s) for small molecules. The previous experimentally determined hot spot residues, Q54 and E177 in HLA-A2, were also predicted to be the dominant residues for binding to E3-19K by our theoretical calculations. Several other residues were also found to play pivotal roles for the binding of E3-19K with HLA-A2. Residues adjacent to E177, including Q54 and several other residues theoretically predicted to be crucial in HLA-A2 were selected as a potential binding pocket to perform virtual screening with 1200 compounds from the Prestwick library. Seven hits were validated by surface plasmon resonance (SPR) as binders to HLA-A2 as a first step in identifying molecules that can perturb its association with the Ad E3-19K protein.