1. Must have a diagnosis of metastatic melanoma with measurable disease
2. No prior alpha interferon therapy in the past 12 months or for metastatic disease in the past 30 days
3. Must have an ECOG performance status of 0 or 1
4. Must have a life expectancy of 3 months
5. Must have recovered from toxicity of any radiation therapy given in time period exceeding 28 days from the start of treatment 
6. Must not have had general anesthesia in the 28 days prior to treatment
7. Must have adequate bone marrow, liver and kidney organ function
8. Must meet guidelines for treatment of metastatic disease.

Drugs used in chemotherapy, such as carboplatin and paclitaxel, work in different ways to stop the growth of tumor cells, either by killing the cells or by stopping them from dividing and growing. Sorafenib (also known as BAY 43-9006) may stop the growth of tumor cells by blocking some of the enzymes needed for cell growth and by blocking blood flow to the tumor. It is not yet known whether carboplatin and paclitaxel together with sorafenib is more effective than carboplatin and paclitaxel alone (without sorafenib) in treating melanoma. The purpose of this study is to find out if adding sorafenib to the treatment will benefit patients with stage III or stage IV melanoma that has spread or cannot be treated with surgery. Patients will be randomly assigned to one of two treatment groups. In one group, patients will receive paclitaxel and carboplatin. They will also receive sorafenib by mouth. Patients in the other group will receive paclitaxel and carboplatin but this group will also receive a placebo instead of sorafenib. 

1. Stage III or Stage IV melanoma not amenable to surgery 
2. Be at least 18 years of age
3. Have measurable disease
4. Have no brain metastasis or other
5. current malignancies (cancers)
6. Have no ocular melanoma
7. Have normal kidney and liver function

1. Patients must have a biopsy-proven diagnosis of Merkel Cell Carcinoma that is distantly metastatic or unresectable.
2. Patients with symptomatic, unstable or untreated brain metastases are not eligible.
3. Patients may not have received radiotherapy, chemotherapy or any other investigational drug for any reason 28 days prior to entry into the study.
4. Patients may not have had a major surgery within 14 days before entry into the study,
5. Patients must not have a severe and/or uncontrolled concurrent medical disease such as diabetes, chronic renal or liver disease of active uncontrolled infection.
6. Patients must not be taking therapeutic dishes of coumadin (warfarin) as anticoagulation at the time of entry into the study.
7. Patients must have adequate bone marrow, liver and kidney function.

1. Patients must have histologically proven melanoma.
2. Patients must not have brain metastases.
3. Patients current disease may be previously untreated or have received up to 2 prior systemic therapies for metastatic disease. 
4. Prior interferon use adjuvantly or for metastatic disease is permitted. Prior therapy must have been discontinued at least 4 weeks before registration.
5. Patients must have normal bone marrow, kidney and liver function.

1. Melanoma of a cutaneous origin. Initial presentation of primary melanoma.
2. No clinically palpable lymphadenopathy
3. Must be one of the following: T₃N₀M₀, T₄N₀M₀, T_1-4N₁
4. Must be within 70 days of wide excision and no longer than 84 days after initial biopsy
5. No evidence of incompletely resected melanoma or any distant metastatic disease
6. Must not have autoimmune disorders, conditions of immunosuppression or be on systemic corticosteroids
7. No history of active ischemic heart disease, cerebrovascular disease or congestive heart failure
8. No prior chemotherapy or immunotherapy
9. ECOG performance status 0-1 within 8 weeks of randomization
10. Adequate hematologic and liver function
11. Must not have any significant medical or surgical condition or require any medication or treatment regimen

1. Must have completely resected melanoma which falls into one of the following categories: a) cutaneous melanoma with clinically evident satellites or intransit disease, b) stage III melanoma with gross extracapsular extension, c) mucosal melanoma with nodal involvement, or d) stage IV cutaneous, ocular, or mucosal melanoma, e) any locoregional recurrence after prior adjuvant interferon or failure on S0008, f) any local recurrence of disease after adequate surgical excision of the original primary, g) recurrence in a previously resected nodal basin,       h) four or more involved lymph nodes or matted lymph nodes, i) an ulcerated primary melanoma and any involved lymph nodes (Note: a,b,g,h, and i must be ineligible for S0008 or medically unfit to receive standard high dose interferon
2. Must be within 16 weeks of surgical resection
3. No prior treatment with GM-CSF or any peptides
4. ECOG performance status 0-1
5. No active infection or serious concurrent medical condition
6. Adequate liver and hematologic function
7. Patients that have had multiple primary melanomas are eligible
8. Patients who are eligible for S0008 are strongly encouraged to participate in that study