The incidence of benign lymphoepithelial lesions of the parotid gland in patients afflicted with HIV has increased. Enucleation is a safe and effective procedure that provides the patient with complete removal of the cyst and a low recurrence rate. Enucleation of these parotid cysts should be considered in treating these patients.