Vinca alkaloids are used widely in the treatment of both childhood and adult cancers. Their cellular target is the β-tubulin subunit of α/β-tubulin heterodimers, and they act to inhibit cell division by disrupting microtubule dynamics. Despite the effectiveness of these agents, drug resistance is a major clinical problem. To identify the underlying mechanisms behind vinca alkaloid resistance, we have performed high resolution differential proteome analysis. Treatment of drug-sensitive human leukemia cells (CCRF-CEM) with vincristine identified numerous proteins involved in the cellular response to vincristine. In addition, differential protein expression was analyzed in leukemia cell lines selected for resistance to vincristine (CEA/VCR R) and vinblastine (CEM/VLB100). This combined proteomic approach identified 10 proteins altered in both vinca alkaloid response and resistance: β-tubulin, α-tubulin, actin, heat shock protein 90β, 14-3-3τ, 14-3-3ε, L-plastin, lamin B1, heterogeneous nuclear ribonuclear protein-F, and heterogeneous nuclear ribonuclear protein-K. Several of these proteins have not previously been associated with drug resistance and are thus novel targets for elucidation of resistance mechanisms. In addition, seven of these proteins are associated with the tubulin and/or actin cytoskeletons. This study provides novel insights into the interrelationship between the microtubule and microfilament systems in vinca alkaloid resistance.