In a search for new anti-HIV-1 chemotypes, we developed a multistep ligand-based virtual screening (VS) protocol combining machine learning (ML) methods with the privileged structures (PS) concept. In its learning step, the VS protocol was based on HIV integrase (IN) inhibitors fetched from the ChEMBL database. The performances of various ML methods and PS weighting scheme were evaluated and applied as VS filtering criteria. Finally, a database of 1.5 million commercially available compounds was virtually screened using a multistep ligand-based cascade, and 13 selected unique structures were tested by measuring the inhibition of HIV replication in infected cells. This approach resulted in the discovery of two novel chemotypes with moderate antiretroviral activity, that, together with their topological diversity, make them good candidates as lead structures for future optimization.