The process of HIV entry begins with the binding of the viral envelope glycoprotein gp120 to both the CD4 receptor and one of CXCR4 or CCR5 chemokine coreceptors. There is currently considerable interest in developing novel ligands which can attach to these coreceptors and hence block virus-cell fusion. This article compares the application of structure-based (docking) and ligand-based (QSAR analyses, pharmacophore modeling, and shape matching) virtual screening tools to find new potential HIV entry inhibitors for the CXCR4 receptor. The comparison is based on retrospective virtual screening of a library containing different known CXCR4 inhibitors from the literature, a smaller set of active CXCR4 inhibitors selected from a large combinatorial virtual library and synthesized by us, and some druglike presumed inactive molecules as the reference set. The enrichment factors and diversity of the retrieved molecular scaffolds in the virtual hit lists was determined. Once the different virtual screening approaches had been validated and the best parameters had been selected, prospective virtual screening of our virtual library was applied to identify new anti-HIV compounds using the same protocol as in the retrospective virtual screening analysis. The compounds selected using these computational tools were subsequently synthesized and assayed and showed activity values ranging from 4 to 0.022 μg/mL.