A paraganglioma is a rare tumor composed of chromaffin cells. Malignant paraganglioma is a very rare presentation diagnosed by local recurrence after total resection of the primary mass or findings of distant metastasis. We report a case of a 30-year-old man who had undergone a carotid body tumor resection 10 years before and who presented to us with recurrence of the tumor associated with lymph node, vertebra and skull metastasis. The diagnosis of malignant paraganglioma was based on loco-regional and distant metastasis.