Pts must have previously untreated multiple myeloma and not immediately be planning to undergo autologous stem cell transplant, with a measurable M-protein. Pts with non-secretory multiple myeloma are not eligible. Pts must have received no prior therapy for multiple myeloma, except localized radiation, provided this was not the sole site of evaluable disease. Pts must be greater than or equal to 18 years of age. Pts must have adequate liver, kidney and marrow function as defined per the protocol. Pts must not have uncontrolled, active infection requiring intravenous antiobiotics, NYHA Class III or Class IV heart failure, myocardial infarction within the last 6 months, history of treatment for clinically significant ventricular cardiac arrhythmias, poorly controlled hypertension, poorly controlled diabetes mellitus, or other serious or psychiatric illness that could potentially interfere with the completion of treatment according to this protocol. Pts must have undergone an EKG within 28 days prior to registration. Zubrod PS of 0-3. Females of childbearing potential must have 2 negative pregnancy tests. The first test must be performed within 10-14 days prior to initiation of therapy, and the second test within 24 hours prior to initiating CC-5013. During CC-5013 therapy, pregnancy tests will be required every week for the first 4 weeks, then every 4 weeks if the pt has regular menstruation, or every 2 weeks if the pt's periods are irregular. Effective contraception must be used by pts for at least 4 weeks before beginning treatment, during treatment, during dose interruptiona and for 4 weeks following discontinuation of treatment. Reliable contraception is indicated even where there has been a history of infertility, unless due to hysterectomy or because the pt has been postmenopausal naturally for at least 24 consecutive months. Two reliable forms of contraception must be used simultaneously unless continuous abstinence from heterosexual contact is the chosen method. Females of childbearing potential should be referred to a qualified provider of contraceptive methods, if needed. Sexually mature females who have not undergone a hysterectomy or who have not been postmenopausal naturally for at least 24 consecutive months ar considered to be females of childbearing potential. A prescription for CC-5013 for a female of childbearing potential must not be issued by the prescriber until negative pregnancy tests have been verified by the prescriber. Male pts: It is not known whether CC-5013 is present in the semen of pts receiving the drug. Therefore, males must always use a latex condom during any sexual contact with females of childbearing potential even if they have undergone a successful vasectomy. The pt must use at least one highly effective method and one additional effective method at the same time. If the pt has sex without birth control or if for any reason the pt thinks she may be pregnant, she must immediately stop taking CC-5013 and immediately tell the doctor. No prior malignancy is allowed except for adequately treated basal cell or squamous cell skin cancer, in situ cervical cancer, in situ breast cancer, or other cancer for which the pt has been disease free for at least 3 years. Institutions must have IRB approval of S0309. Pts must be offered participation in S0309. Institutions must have IRB approval of S0334. Pts must be offered participation in S0334. Pts who are unable to take either aspirin 325 mg/day by mouth or alternatively, enoxaparin 40 mg subcutaneously once per day, as a form of thrombotic prophylaxis are not eligible for this study unless they are already on therapeutic anti-coagulation.