Inclusion Criteria:

- Histological or cytological confirmed melanoma that is metastatic or unresectable;
patients must have a history of cutaneous, mucosal or unknown primary site

- Patients who have received prior systemic cytotoxic chemotherapy for treatment of
melanoma are ineligible; the following groups are eligible with regard to prior
systemic therapy either in the adjuvant or metastatic disease setting:

- No prior therapy

- Immunotherapy consisting of Interferon, Interleukin-2, GM-CSF or vaccine

- One prior investigational therapy (cannot be chemotherapy or an inhibitor of
Ras, Raf, or MEK) NOTE: Chemotherapy given via isolated limb perfusion is
allowed

- Prior radiation therapy is allowed; however, if radiation has been administered to a
lesion, there must be radiographic evidence of progression of that lesion in order
for that lesion to constitute measurable disease or to be included in the measured
target lesions

- All sites of disease must be evaluated within 4 weeks of registration; patients must
have measurable disease as defined by RECIST

- ECOG performance status of 0 or 1

- White blood count >= 3,000/mm^3

- Absolute granulocyte count >= 1,500/mm^3

- Platelet count >= 100,000/mm^3

- Serum creatinine =< 2.0 x upper limit of normal (ULN) or serum creatinine clearance
(CrCl) >= 40ml/min (neither drug is cleared by the kidney)

- Total Bilirubin =< 1.5 x ULN (< 3.0 x ULN in the presence of Gilbert's disease)

- INR =< 1.5 and a PTT within normal limits (patients who are on therapeutic
anticoagulation with warfarin should have documentation of a normal PT/PTT prior to
initiating that therapy)

- Patients must not have ocular melanoma

- Patients must have discontinued immunotherapy or radiation therapy at least 4 weeks
prior to initiation of treatment and recovered from adverse events due to those
agents

- Patients must not receive any other investigational agents during the period on study
or the four weeks prior to initiation of treatment

- Patients must not have a history or clinical evidence of brain metastasis; patients
must be evaluated with a head MRI within 4 weeks prior to enrollment

- Patients must not have other current malignancies, other than basal cell skin cancer,
squamous cell skin cancer, in situ cervical cancer, ductal or lobular carcinoma in
situ of the breast; patients with other malignancies are eligible if they have been
continuously disease free for >= 5 years prior to the time of randomization

- Patients must not have any evidence of bleeding diathesis

- Patients must not have a serious intercurrent illness including, but not limited to,
ongoing or active infection requiring parenteral antibiotics, clinically significant
cardiovascular disease (e.g. uncontrolled hypertension, myocardial infarction,
unstable angina), New York heart association grade II or greater congestive heart
failure, serious cardiac arrhythmia requiring medication, or grade II or greater
peripheral vascular disease within 1 year prior to study entry, or psychiatric
illness/social situations that would limit compliance with study requirements

- Patients must not be taking cytochrome P450 enzyme-inducing antiepileptic drugs
(phenytoin, carbamazepine or phenobarbital), rifampin or St. John's Wort

- Women must not be pregnant or breast-feeding as the agents used in this study may be
teratogenic to a fetus and there is no information on the excretion of the agents or
their metabolites into breast milk

- All females of childbearing potential must have a blood test or urine study within 4
weeks prior to registration to rule out pregnancy

- The effects of sorafenib, carboplatin and paclitaxel on the developing human fetus
are unknown; for this reason and because antiangiogenic agents as well as other
therapeutic agents used in this trial are known to be teratogenic, women of
child-bearing potential and men must agree to use adequate contraception (hormonal or
barrier method of birth control; abstinence) prior to study entry and for the
duration of study participation; should a woman become pregnant while participating
in this study, she should inform her treating physician immediately; if a man
impregnates a woman while participating in this study, he should inform his treating
physician immediately as well

- HIV-positive patients are excluded from the study. For patients receiving combination
anti-retroviral therapy, the potential impact of pharmacokinetic interactions with
sorafenib, carboplatin or paclitaxel is unknown; appropriate studies may be
undertaken in patients with HIV and those receiving combination anti-retroviral
therapy in the future