The outbreak of a novel febrile respiratory disease called COVID-19, caused by a newfound coronavirus SARS-CoV-2, has brought a worldwide attention. Prioritizing approved drugs is critical for quick clinical trials against COVID-19. In this study, we first manually curated three Virus-Drug Association (VDA) datasets. By incorporating VDAs with the similarity between drugs and that between viruses, we constructed a heterogeneous Virus-Drug network. A novel Random Walk with Restart method (VDA-RWR) was then developed to identify possible VDAs related to SARS-CoV-2. We compared VDA-RWR with three state-of-the-art association prediction models based on fivefold cross-validations (CVs) on viruses, drugs and virus-drug associations on three datasets. VDA-RWR obtained the best AUCs for the three fivefold CVs, significantly outperforming other methods. We found two small molecules coming together on the three datasets, that is, remdesivir and ribavirin. These two chemical agents have higher molecular binding energies of − 7.0 kcal/mol and − 6.59 kcal/mol with the domain bound structure of the human receptor angiotensin converting enzyme 2 (ACE2) and the SARS-CoV-2 spike protein, respectively. Interestingly, for the first time, experimental results suggested that navitoclax could be potentially applied to stop SARS-CoV-2 and remains to further validation.