Tobacco can easily accumulate cadmium (Cd) in leaves and thus poses a potential threat to human health. Cd-stress-hydroponic-experiments were performed, and the proteomic and transcriptional features of two contrasting tobacco genotypes Yun-yan2 (Cd-tolerant) and Guiyan1 (Cd-sensitive) were compared. We identified 18 Cd-tolerance-associated proteins in leaves, using 2-dimensional gel electrophoresis coupled with mass spectrometry, whose expression were significantly induced in Yunyan2 leaves but down-regulated/unchanged in Guiyan1, or unchanged in Yunyan2 but down-regulated in Guiyan1 under 50 µM Cd stress. They are including epoxide hydrolase, enoyl-acyl-carrier-protein reductase, NPALDP1, chlorophyll a-b binding protein 25, heat shock protein 70 and 14-3-3 proteins. They categorized as 8 groups of their functions: metabolism, photosynthesis, stress response, signal transduction, protein synthesis, protein processing, transport and cell structure. Furthermore, the expression patterns of three Cd-responsive proteins were validated by quantitative real-time PCR. Our findings provide an insight into proteomic basis for Cd-detoxification in tobacco which offers molecular resource for Cd-tolerance.