A slow-growing, painless submandibular swelling with calcified material of adult usually impresses diagnoses as sialadenitis with sialoliths. However, it can be a hemangioma with phleboliths, although it is rare. We reported a case of a 65-year-old female patient who had been found a large cavernous hemangioma with phleboliths of her submandibular region. Computed tomography (CT) revealed the extent of the mass and phleboliths detection to establish the diagnosis before treatment. Treatment planning is based on tumor location, extent, growth rate, accessibility, patient's age, and esthetics. Surgical excision is performed to remove the hemangioma completely because of no contraindication for operation. Careful dissection was done to avoid massive hemorrhage. The post-operation status of the patient was smooth without severe complication. No evidence of recurrence was found during post-operative follow-up of 4 months.