This is a prospective, randomized, parallel-group, open-label phase III, on an intention to treat, multicenter study. The main endpoint is time-to-failure (TTP=time to progression). The power is based on an initial assumption of a median TTP of 1.5 years in the experimental (Velcade) group and 1 year in the control group. The design of the study is group sequential. There will be 4 interim analyses and one final analysis. The study is designed to have a priori 90% power to detect the clinically relevant difference at completion of the study at 0.025 level. Patients with multiple myeloma whose disease has either progressed or relapsed at least one year after one or two autologous transplantations will be enrolled. Prior to random assignment, subjects will be stratified on center and number of autologous transplants.Subjects will be randomly assigned to treatment in a 1: 1 allocation within each stratum to Velcade plus Thalidomide plus Dexamethasone (VTD) or Thalidomide plus Dexamethasone. Velcade 1.3 mg/m2 will be given as an i.v. bolus on Days 1, 4, 8 and 11 followed by a 10-day rest period (Days 12 to 21) for 8 cycles (6 months) and then on Days 1, 8, 15, and 22 followed by a 20-day rest period (Days 23 to 42) for 4 cycles (6 months). In both arms, Thalidomide will be given at 200 mg/day per os for one year and Dexamethasone 40 mg/day per os four days every three weeks for one year.Treatment will continue until disease progression, or the occurrence of unacceptable treatment-related toxicity, or up to a total of 12 cycles of Velcade except for those subjects who have a continuing decrease in the levels of paraprotein after 12 cycles. These subjects may continue for as long as treatment is tolerated, and they continue to respond. If a subject has a CR, then treatment should continue at least 2 cycles after the objective response is confirmed. For subjects with a PR or stable disease, treatment may continue after a maximum objective response is confirmed unless the subject experiences unacceptable treatment-related toxicity or the subject has completed 12 cycles of treatment. Disease assessment will occur at the start of each cycle. If a subject discontinues treatment without disease progression, disease assessment will be performed every 3 weeks for 48-weeks from the start of the first dose of study entry drug. Subjects who have not progressed at the end of 48-week follow up period will be assessed every 6 weeks until disease progression is documented