Introduction: β-Tubulin is an important target for the binding of anti-cancer drugs, in particular, paclitaxel (taxol), vinblastine and epothilone. However, mutations in β-tubulin structure give resistance to chemotherapeutic agents. Notably, mutations at R306C, F270 V, L217R, L228F, A185T and A248V positions in β-tubulin give high resistance for paclitaxel binding. Objective: To discover novel inhibitors of β-tubulin from natural sources, particularly alkaloids, using a virtual screening approach. Methodology: A virtual screening approach was employed to find potent lead molecules from the Naturally-occurring Plant-based Anti-cancer Compound-activity Target (NPACT) database. Alkaloids have great potential to be anti-cancer agents. Therefore, we have screened all alkaloids from a total of 1574 molecules from the NPACT database for our study. Initially, Molinspiration and DataWarrior programs were utilised to calculate pharmacokinetics and toxicity risks of the alkaloids, respectively. Subsequently, AutoDock algorithm was employed to understand the binding efficiency of alkaloids against β-tubulin. The binding affinity of the docked complex was confirmed by means of an intermolecular interaction study. Moreover, oral toxicity was predicted by using ProTox program. Further, metabolising capacity of drugs was studied by using SmartCYP software. Additionally, scaffold analysis was done with the help of scaffold trees and dendrograms, providing knowledge about the building blocks for parent-compound synthesis. Results: Overall, the results of our computational analysis indicate that isostrychnine, obtained from Strychnosnux-vomica, satisfies pharmacokinetic and bioavailability properties, binds efficiently with β-tubulin. Thus, it could be a promising lead for the treatment of paclitaxel resistant cancer types. Conclusion: This is the first observation of inhibitory activity of isostrychnine against β-tubulin and warrants further experimental investigation. Copyright © 2016 John Wiley & Sons, Ltd. Copyright © 2016 John Wiley & Sons, Ltd.