Subjects will receive immunizations every other week for 8 immunizations prior to clinical and immunological evaluations. Patients will then receive immunizations every month up to one year. Cyclophosphamide will be administered intravenously 3 days prior to the first immunization, 3rd, 5th, 7th, 9th, and subsequent monthly immunizations. Women and men >= 18 years of age with refractory metastatic malignancies that express NY-ESO-1 by RT-PCR or immunohistochemistry. Alternatively, patients may be elected on the basis of serum anti-NY-ESO-!-antibodies as detected by ELISA.

Primary Objective: To evaluate the toxicity profile of the regimens described in Section 1.6.

Secondary Objective: To detect and quantitate immune responses induced by the proposed peptide vaccine or protein vaccine in association with CpG 7909 and cyclophosphamide. This endpoint will be assessed by an IFN-y ELISPOT assay of NY-ESO-1-specific tumor-reactive CD8 + T cells. We also will look for NY-ESO-1 tetramer CD8+ T cells, Delayed-type Hypersensitivity (DTH), and NY-ESO-1-specific CD4+ T cell responses with ELISPOT assays and cytokine-release-assays.

Tertiary Objectives: To evaluate tumor response in terms of clinical tumor regression and progression-free interval. To evaluate the survival of patients treated with the regimens described in Section 1.6.

The first 3 patients will be assigned treatment A. All three patients will be treated and observed for one month. If no DLTs are observed in the first 3 patients, accrual to arm A will be put on hold and accrual will continue with Arm B. However, if 1 DLT is observed in Arm A, up to 3 additional patients will be treated on Arm A, until either 2 DLTs have been observed, or 6 patients have been treated with just 1 DLT among them. If 2 DLTs are observed in Arm A, the study will terminate and all treatments will be deemed intolerable. The same principles apply to the cohorts treated on B-E: if the number of DLTs (after one month of treatment) is zero, accrual proceeds to the next treatment group; if it is 1, accrual continues with the same treatment for up to 3 additional patients; if it is 2, no patients will be treated on the remaining treatment arms.

Inclusion Criteria:

1. Written informed consent obtained prior to the initiation of study procedures.
2. Male and female subjects >= 18 years of age.
3. Measurable disease as defined by the Response Evaluation Criteria in Solid Tumors (RECIST).
4. Tumor must express NY-ESO-1 as determined by RT-PCR or immunohistochemistry. Subjects with anti-NY-ESO-1 antibodies measured by ELISA, will also be eligible for this trial.
5. No specific HLA expression required but we will systematically perform for each patient genotypic HLA typing.
6. Negative serology tests for HIV 1 and 2, Hepatitis B and C.
7. Adequate hematologic, renal, and liver function as evidenced by the following: - WBC >= 3,000 / mm3; - lymphocytes >= 1,000 / mm3; - platelets >= 100,000 / mm3; - serum creatinine <= 1.5 x upper limit of normal (ULN); - Serum Bilirubin <= 1.5 x ULN; - Serum AST / ALT <= 2.5 x ULN.
8. Subjects with stage III/IV cancer will be eligible after they have progressed after receiving any available and well-established life-prolonging therapy.
9. Subjects with melanoma must have histologically confirmed measurable Stage III or Stage IV melanoma (according to the current AJCC 6th edition classification). Cutaneous, ocular and mucosal melanoma will be eligible.
10. Subjects with Stage III or Stage IV prostate cancers who have received and not responded to radiation therapy, surgery (if applicable) and hormonal therapy, and are hormone-refractory. Subjects must have two consecutive PSA values, at least 14 days apart, each >= 5 ng/ml and >= 50% above the minimum PSA observed during castration therapy or above the pretreatment value if there was no response.
11. Subjects with Stage III or Stage IV breast cancers who have received and not responded to radiation therapy (if applicable), hormonal therapy (if ER+) and two regimens of standard chemotherapy.
12. Subjects with Stage III or Stage IV NSCLC lung cancers who have received and not responded to radiotherapy (if applicable), surgery (if applicable), and at least one regimen of standard chemotherapy.
13. Subjects with locally advanced metastatic bladder cancers who have received and not responded to radical cystectomy (if applicable), radiation therapy (if applicable), and at least one combination chemotherapy regimen.
14. Subjects with Stage III or Stage IV head and neck cancers who have received and not responded to radiotherapy, surgery, and at least one regimen of chemotherapy combinations.
15. Subjects with Stage III or Stage IV soft tissue sarcomas who have received and not responded to radiotherapy, surgery, and at least one regimen of chemotherapy combinations.
16. Subjects with Stage III or Stage IV ovarian cancer who have received and progressed after surgery and at least one regimen of standard chemotherapy combinations.
17. Subject with Stage III multiple myeloma who have received at least two regimens for relapsed and / or refractory multiple myeloma including bortezomib or velcade.
18. Subjects must have fully recovered from surgery, and must not have received any chemotherapy, hormonal therapy, radiotherapy, or biological therapy within the preceding 4 weeks.
19. Life expectancy of at least 6 months.
20. WHO Performance Status of 0 or 1.
21. Normal titers for ANA (<= 1/80) and anti-ds DNA (<= 1/10). Patients with elevated titers of ANAs (> 1/80) or anti-ds DNA (>1/10) will be excluded from protocol only if they have symptoms of active auto-immune disease as assessed by specialized consultation (rheumatologist).
22. Subjects need to have recovered from any effects of previous treatments (recovery must have been documented for at least 1 week prior to treatment on this study).
23. Subjects must be free of brain metastasis by contrast-enhanced CT/MRI scans or have brain metastasis and: the total number of brain metastasis is <=3; each brain metastasis must have been either completely removed by surgery of treated with stereotactic radiosurgery (gamma knife); the subject must be asymptomatic for more than 1 month.
24. Female subjects of child bearing potential must have a negative pregnancy test, and must not be breast feeding.
25. Subjects must agree to use effective contraception (both males and females). We have decided to include patients with NY-ESO-1-expressing tumors of different histological types and not only melanoma as we have previously done in the ongoing trial UPCI 00-079. The reasons are several-fold. First, we do not expect that the type of disease will have an impact on the main objectives (i.e. safety, toxicity and immunological). Second, we feel it is important to be able to include all eligible cancer patients with no available therapeutic option and who are willing to be included in a novel investigative trial. Finally, our experience with the ongoing trial UPCI 00-079 leads us to think that the large majority of patients will be melanoma patients (17 patients included to date, including 16 melanoma patients and one sarcoma patient).

Exclusion Criteria:

1. Subjects with prostate cancer who demonstrate an anti-androgen withdrawal response, defined as a >= 25% drop in PSA within 4 weeks (flutamide) or six week (nilutamide, bicalutamide) of stopping a non-steroidal anti-androgen are not eligible until the PSA rises above the nadir observed after anti-androgen withdrawal.
2. Serious illnesses, such as: cardiovascular disease (uncontrolled congestive heart failure, hypertension, cardiac ischemia, myocardial infarction, severe cardia arrhythmia), bleeding disorders, autoimmune diseases, severe obstructive or restrictive pulmonary diseases, active systemic infections, inflammatory bowel disorders, severe renal disease.
3. Any significant psychiatric disease, medical intervention, or other condition, which in the opinion of the principal investigator, could prevent adequate informed consent or compromise participation in the clinical trial.
4. Active infection or antibiotics within one-week prior to study, including unexplained fever (temp > 38.1 degree C).
5. Treatment with nitrosources within 6 weeks prior to enrollment.
6. Systemic steroid or other immunosuppressive therapy > 10 days within 4 weeks of enrollment.
7. A requirement for systemic immunosuppressive therapy > 5 days developing during the trial will result in the subject being removed from the study.
8. Treatment with any investigational immunization with CpG 7909 and NY-ESO-1 peptides of NY-ESO-1 protein within two years of registration or treatment with any other investigational product within 28 days of registration.