The goal of this clinical research study is to learn if lenalidomide in combination with prednisone can help to control myelofibrosis. The safety of lenalidomide and prednisone for the treatment of myelofibrosis will also be studied.

Lenalidomide is designed to change the body's immune system. It may also interfere with the development of tiny blood vessels that help support tumor growth. Therefore, in theory, it may decrease or prevent the growth of cancer cells. Prednisone is designed to improve the results of lenalidomide and to help reduce the side effects.

If you are found to be eligible to take part in this study, you will take 1-2 capsules of lenalidomide by mouth daily. You will take lenalidomide daily for 21 days followed by 1 week rest. This 28-day period is called a study "cycle."

Swallow lenalidomide capsules whole with water at the same time each day. Do not break, chew or open the capsules.

If you miss a dose of lenalidomide, take it as soon as you remember on the same day. If you miss taking your dose for the entire day, take your regular dose the next scheduled day (do NOT take double your regular dose to make up for the missed dose).

You will take prednisone by mouth every day during Cycles 1-2, and every other day during Cycle 3. You may only take prednisone for Cycles 1-3.

You will be given a study drug diary. In this diary, you will record when you take the study drug(s).

During treatment, blood (about 1 tablespoon) will be drawn once every 1-2 weeks. Following the completion of 24 cycles, blood (about 1 tablespoon) will be drawn every 1- 3 months. The tests may be repeated more frequently to check for side effects.

Every month for the first 3 months, and then every 3 months, until you complete 24 cycles, you will have a study visit. You will have a bone marrow biopsy/aspirate every 3 months. Lenalidomide will be provided to you as a monthly (28-day) supply.

Following the completion of Cycle 24, you will have a study visit every 6 months. You will have a bone marrow biopsy/aspirate every 12 months. Lenalidomide will be provided to you as a monthly (28-day) supply.

Depending on side effects and the activity of the study drug against the disease, your dose of the study drug may be increased or decreased.

You may stay on study for as long as you are benefitting. You will be taken off study if you are not or are no longer benefitting or intolerable side effects occur.

This is an investigational study. Lenalidomide and prednisone are both FDA approved and commercially available. Lenalidomide is approved by the Food and Drug Administration (FDA) for the treatment of patients with transfusion-dependent anemia due to Low- or Intermediate-1-risk myelodysplastic syndromes associated with the chromosome 5 abnormality with or without other chromosome abnormalities. Lenalidomide is also approved in combination with dexamethasone for the treatment of patients with multiple myeloma that have received at least one prior therapy. Myelodysplastic syndrome (MDS) and Multiple Myeloma (MM) are cancers of the blood. It is currently being tested in a variety of cancer conditions. In this case it is considered experimental. Prednisone is on the market for many different things but not specifically for Myelofibrosis. The use of these drugs in combination is considered investigational in this study. Up to 41 patients will take part in this study. All will be enrolled at M. D. Anderson.

Inclusion Criteria:

1. Diagnosis of myelofibrosis requiring therapy, including those previously treated and relapsed or refractory, or if newly diagnosed, with intermediate or high risk according to Lille scoring system (risk factors are: Hb < 10 g/dl, White blood count (WBC) < 4 or > 30 x 109/L; risk group: 0 factor(s) = low, 1 factor(s) = intermediate, 2 factor(s) = high) or with symptomatic splenomegaly
2. Understanding and voluntary signing an Institutional Review Board (IRB)-approved informed consent form.
3. Age >/= 18 years at the time of signing the informed consent.
4. Disease-free of prior malignancies for >/= 2-years with exception of basal cell or squamous cell carcinoma of the skin, or carcinoma "in situ" of the cervix or breast.
5. Eastern Cooperative Oncology Group (ECOG) performance status 0 to 2.
6. Patients must have adequate organ function as demonstrated by the following: Total bilirubin </= 2.0 mg/dL (unless higher due to MF); Serum creatinine </= 2.0 mg/dL (unless higher due to MF); Absolute neutrophil count >/= 1 x 10^9/L; Alanine transaminase (ALT) \

For at least 6 cycles, and up to 11 years