The prediction of high-affinity and/or high-specificity protein-glycosaminoglycan (GAG) interactions is an inherently difficult task, due to several factors including the shallow nature of the typical GAG-binding site and the inherent size, flexibility, diversity, and polydisperse nature of the GAG molecules. Here, we present a generally applicable methodology termed Combinatorial Library Virtual Screening (CVLS) that can identify potential high-affinity, high-specificity protein-GAG interactions from very large GAG combinatorial libraries and a suitable GAG-binding protein. We describe the CVLS approach along with the rationale behind it and provide validation for the method using the well-known antithrombin-thrombin-heparin system.