Heparanase is a key enzyme involved in the dissemination of metastatic cancer cells. In this study a combination of in silico techniques and experimental methods was used to identify new potential inhibitors against this target. A 3D model of heparanase was built from sequence homology and applied to the virtual screening of a library composed of 27 known heparanase inhibitors and a commercial collection of drugs and drug-like compounds. The docking results from this campaign were combined with those obtained from a pharmacophore model recently published based in the same set of chemicals. Compounds were then ranked according to their theoretical binding affinity, and the top-rated commercial drugs were selected for further experimental evaluation. Biophysical methods (NMR and SPR) were applied to assess experimentally the interaction of the selected compounds with heparanase. The binding site was evaluated via competition experiments, using a known inhibitor of heparanase. Three of the selected drugs were found to bind to the active site of the protein and their KD values were determined. Among them, the antimalarial drug amodiaquine presented affinity towards the protein in the low-micromolar range, and was singled out for a SAR study based on its chemical scaffold. A subset of fourteen 4-arylaminoquinolines from a global set of 249 analogues of amodiaquine was selected based on the application of in silico models, a QSAR solubility prediction model and a chemical diversity analysis. Some of these compounds displayed binding affinities in the micromolar range.