Microtubules are among the most studied and best characterized cancer targets identified to date. Many microtubule stabilizers have been introduced so far that work by disrupting the dynamic instability of microtubules causing mitotic block and apoptosis. However, most of these molecules, especially taxol and epothilone, suffer absorption, toxicity and/or resistance problems. Here we employ a novel similarity-based virtual screening approach in the hope of finding other microtubule stabilizers that perform better and have lower toxicity and resistance. Epothilones, discodermolide, eleutherobin and sarcodictyin A have been found to compete with taxanes for the β-tubulin binding site, which suggests common chemical features qualifying for that. Our approach was based on similarity screening against all these compounds and other microtubule stabilizers, followed by virtual screening against the taxol binding site. Some novel hits were found, together with a novel highly rigid molecular scaffold. After visual manipulations, redocking and rescoring of this novel scaffold, its affinity dramatically increased in a promising trend, which qualifies for biological testing.