The disruption of crucial interactions between HIV-1 Integrase and cellular cofactor LEDGF/p75 represents an emerging approach for the design and development of new antiretroviral agents. In this study we report the successful application of a structure-based virtual screening strategy for the discovery of natural hit structures able to inhibit Integrase-LEDGF/p75 interaction. The application of sequential filters (drug-likeness, 3D-pharmacophore mapping, docking, molecular dynamics simulations) yielded a hit list of compounds, out of which 9 were tested in the in vitro AlphaScreen assays and 8 exhibited a detectable inhibition of the interaction between the two proteins. The best inhibitors belong to different chemical classes and could be represent a good starting point for further optimization and structure-activity relationship studies.