Paroxysmal hemicrania (PH) has been recently defined as an uncommon primary headache. PH is characterized by frequent attacks of severe unilateral pain associated with autonomic symptoms. The attack frequency usually ranges from 5 to 40 attacks per day. PH is characterized by its absolute responsiveness to indomethacin. However, indomethacin is not often well tolerated because of its gastric side effects. We report two patients with PH who could not tolerate indomethacin due to its severe gastric side effects but dramatically responded to rofecoxib.