Inclusion Criteria

Concurrent Medication:

Allowed:

• Non-steroidal agents such as acetaminophen for drug-related fevers.
• Pentamidine inhalation prophylaxis for Pneumocystis carinii pneumonia (PCP) in patients with a prior history or a T4 count < 200 cells/mm3.
• Antiemetics for nausea, vomiting.
• Symptomatic treatment for grades 1 and 2 oral toxicity.
• Toxicity grades according to NIAID Recommendations for Grading Acute and Subacute Toxic Effects (Adults).

Patients must have newly diagnosed biopsy-proven advanced AIDS-related Kaposi's sarcoma.

Exclusion Criteria

Concurrent Medication:

Excluded:

• Systemic steroids for > 1 week in any 30 days.
• All known marrow-suppressive agents.
• Any other investigational drugs.

Patients will be excluded from the study for the following reasons:

• The presence of other active malignancies except basal cell carcinoma of the skin and in situ uterine cancer.
• Alteration of mental status that may not permit compliance with the protocol.
• Symptomatic sensory or motor neuropathy.
• History of myocardial infarction or significant arrhythmias.
• Class III/IV functional capacity in cardiac patients.

Prior Medication:

Excluded:

• Cytotoxic chemotherapy.

Excluded within 1 week of study entry:

• Therapy for Kaposi's sarcoma, including interferons, immunomodulators, antiretroviral agents.

Patients may not have any of the following diseases or symptoms:

• Allergy to bleomycin.
• The presence of other active malignancies except basal cell carcinoma of the skin and in situ uterine cancer.
• Alteration of mental status that may not permit compliance with the protocol.
• Symptomatic sensory or motor neuropathy.
• History of myocardial infarction or significant arrhythmias.
• Class III/IV functional capacity in cardiac patients.
• Concurrent serious infections, such as Pneumocystis carinii pneumonia (PCP), toxoplasma brain abscess, cytomegalovirus (CMV) retinitis or colitis, cryptococcal meningitis, and symptomatic Mycobacterium avium- intracellulare (MAI).