Leiomyosarcoma of the parotid gland is a rare tumor with only six cases reported in the english literature. To date, the association of this rare tumor with HIV infection has never been reported. We report the first case of a 19-year-old Caribbean woman affected by leiomyosarcoma of the parotid gland and HIV infection. Surgery, radiotherapy and chemotherapy used in this patient did not provide a good result in terms of overall survival. Intercurrent disease, opportunistic infection and chemotherapy cross-reaction have not been reported during this treatment regimen. The ability to use combined modality interventions in patients with secondary malignancies and immunosuppression requires further study with focus on both tolerance and efficacy.