The growth of make-on-demand libraries in recent years has provided completely new possibilities for virtual screening for discovering new hit compounds with specific and favorable properties. However, since these libraries now contain billions of compounds, screening them using traditional methods such as molecular docking has become challenging and requires substantial computational resources. Thus, to take real advantage of the new possibilities introduced by the make-on-demand libraries, different methods have been proposed to accelerate the screening process and prioritize molecules for evaluation. Here, we introduce SpaceGA, a genetic algorithm that leverages the rapid similarity search tool SpaceLight (Bellmann, L.; Penner, P.; Rarey, M. Topological similarity search in large combinatorial fragment spaces. J. Chem. Inf. Model. 2021, 61, 238–251). to constrain the optimization process to accessible compounds within desired combinatorial libraries. As shown herein, SpaceGA is able to efficiently identify molecules with desired properties from trillions of synthesizable compounds by enumerating and evaluating only a small fraction of them. On this basis, SpaceGA represents a promising new tool for accelerating and simplifying virtual screens of ultralarge combinatorial databases.