Inclusion Criteria:

- Histologically documented metastatic melanoma classified as stage IV (AJCC 2002) of
cutaneous origin.

- ≥ 18 years of age

- ECOG performance status of 0 or 1

- Patients should not have received any systemic treatment for stage IV disease (study
= "first-line" treatment).

- Patients with progressive disease (PD) to stage IV under prior treatment with
interferons as well as all patients who have already been treated with Sorafenib
should not be included.

The following are allowed:

- adjuvant interferon treatment (without progressive disease during treatment!) or
vaccine therapy for resected stage I-III disease

- palliative surgery or radiotherapy for stage IV disease

- prior cytokine or chemotherapy treatment for local-regional disease by isolated limb
perfusion or intralesional therapy

- Life expectancy >6 months.

- Patients must have measurable disease defined as >= 1 not pretreated unidimensional
measurable lesion >= 20 mm (conventional techniques) or >= 10 mm by spiral CT/MRI.

Patients must have adequate hematological, renal and liver functions as defined by
laboratory values below performed within 14 days prior to study inclusion:

- absolute neutrophil count (ANC) > 1.5 x 109/l

- platelet count > 100 x 109/l

- hemoglobin > 10 g/dl (> 6.2 mmol/l)

- serum creatinine <= 1.5 x upper limit of institutional values

- total serum bilirubin <= 1.5x upper limit of institutional values

- ALAT and ASAT <= 2.5x upper limit of institutional values (exception: liver
metastases)

In addition:

- Patients should not suffer from frequent vomiting or medical conditions which could
interfere with oral medication intake.

- Negative pregnancy test of women of childbearing potential performed within 7 days
prior to the start of treatment.

- Women of childbearing potential must agree to use an effective method of
contraception (Pearl-Index < 1, e.g. hormonal contraception including the combined
oral contraceptive pill, the transdermal patch, and the contraceptive vaginal ring,
intrauterine devices or sterilization) during treatment and for at least 6 months
thereafter.

- Men must agree to use an effective method of contraception during treatment and for
at least 6 months thereafter.

- Patients should understand the informed consent and will need to sign the consent

Exclusion Criteria:

- Ocular or mucosal melanoma.

- History or evidence of brain metastasis.

- Patients with LDH values higher than 2x upper limit of institutional values.

- Patients with thyroid dysfunctions not responsive to therapy.

- Patients with uncontrolled diabetes mellitus.

- Patients with prior or active autoimmune disease or autoimmune hepatitis.

- Cardiac disease: congestive heart failure > class II NYHA, patients must not have
unstable angina or new onset of angina or myocardial infarction within the past 6
months. Cardiac ventricular arrhythmias requiring antiarrhythmic therapy.

- Uncontrolled hypertension defined as systolic blood pressure > 150 mm Hg or diastolic
pressure > 90 mm Hg, despite optimal management.

- Active clinically serious infections > CTCAE Grade 2.

- Patients who are HIV positive or have AIDS.

- Thrombotic or embolic events including transient ischemic attacks within the past 6
months.

- Evidence or history of bleeding diathesis or coagulopathy.

- Therapeutic anticoagulation with Vitamin K antagonists such as warfarin, or with
heparins or heparinoids. Low dose warfarin is permitted if INR is < 1.5. Low dose
aspirin is permitted.

- Known or suspected allergy to Sorafenib or any ingredient of Sorafenib or PEG-IFN-α
-2b or any ingredient of PEG-IFN-α -2b or to any interferone.

- Previous cancer that is distinct in primary site or histology from melanoma except
cervical cancer in situ, treated basal cell carcinoma, superficial bladder tumors or
any cancer curatively treated 3 years prior to study entry.

- Substance abuse, medical or psychological condition that may interfere with the
patient´s participation in the study.

- Patients with medication requiring chronic systemic corticosteroids.

- Patients with prior systemic anticancer treatment in the last 2 weeks.

- Patients with severe liver disease or severe renal disease.

- Patients with seizure disorders requiring anticonvulsant therapy.

- Patients with any severe debilitating diseases.