Skp2 is overexpressed in multiple cancers and plays a critical role in tumor development through ubiquitin/proteasome-dependent degradation of its substrate proteins. Drugs targeting Skp2 have exhibited promising anticancer activity. Here, we identified a plant-derived Skp2 inhibitor, betulinic acid (BA), via high-throughput structure-based virtual screening of a phytochemical library. BA significantly inhibited the proliferation and migration of non-small cell lung cancer (NSCLC) through targeting Skp2-SCF E3 ligase both in vitro and in vivo. Mechanistically, BA binding to Skp2, especially forming H-bonds with residue Lys145, decreases its stability by disrupting Skp1-Skp2 interactions, thereby inhibiting the Skp2-SCF E3 ligase and promoting the accumulation of its substrates; that is, E-cadherin and p27. In both subcutaneous and orthotopic xenografts, BA significantly inhibited the proliferation and metastasis of NSCLC through targeting Skp2-SCF E3 ligase and upregulating p27 and E-cadherin protein levels. Taken together, BA can be considered a valuable therapeutic candidate to inhibit metastasis of NSCLC.