Malignant spindle cell tumors of the parotid gland are a diagnostic challenge. We present an unusual case of such a tumor that occurred in the right parotid gland of a 53-year-old man. The clinical and histologic assessments were consistent with a primary sarcoma of the parotid gland. The tumor was composed of sheets of pleomorphic, spindle-shaped cells with an area of bone formation. By immunohistochemistry, the tumor cells were positive for vimentin and negative for epithelial markers. Electron microscopy revealed mesenchymal cells containing moderate amounts of rough endoplasmic reticulum. The major differential diagnostic considerations were spindle cell carcinoma, carcinosarcoma, and primary undifferentiated sarcoma with osseous metaplasia. The lack of epithelial features and the benign appearance of the bone formation led to a diagnosis of undifferentiated sarcoma of the parotid gland.