A 14-year-old girl was referred for evaluation and management of progressive, painful swelling of the right cheek. Swelling had been present since 3-year old and had gradually increased in size. Magnetic resonance imaging (MRI) revealed a well-circumscribed, brighter mass in the right masseter muscle with numerous rounded areas of signal hypointensity. Preoperative diagnosis was intramuscular hemangioma of the masseter muscle and surgery was performed. The tumor was completely removed except for a few, small phleboliths. Pathological examination of resected tissue led to a high suspicion of cavernous hemangioma with phlebolithiasis. Nine months postoperatively, the patient developed another painful mass in the right masseter muscle. MRI indicated recurrent hemangioma and further surgery was performed. Careful exploration resulted in completely removal of residual phleboliths accompanied with fibroadipose tissue. Part of the buccal branch of the facial nerve was excised to achieve complete resection of the lesion. Histological examination revealed distinct venous formation in phleboliths adjacent to fibroadipose tissue, demonstrating that both phleboliths and feeding vessels had been left by the previous operation. The present report reviews the literature on intramuscular hemangiomas of the masseter muscle, and discusses diagnostic methods and optimal surgical treatment.