Cellular fibrous histiocytoma, a variant of fibrous histiocytoma, is a designation used for lesions showing increased cellularity with a fascicular growth pattern and frequent extension into the subcutis. Here we describe a case of cellular fibrous histiocytoma showing repeated recurrence in a 36-year-old woman who initially presented with a 2-cm cutaneous tumor on her right elbow. Histopathologically, the first resected specimen demonstrated irregularly arranged collagen fibers mixed with scattered proliferating plump to spindle-shaped fibrohistiocytes. However, examination of the resected specimens obtained after recurrence showed that the cellularity had increased, the spindle-shaped cells showing monomorphic proliferation with a fascicular and storiform growth pattern extending into the subcutis, as well as an increase of Ki-67 positivity. Since the lesion showed repeated relapse within a short period, we performed wide-field resection of the tumor with a 3-cm margin. Currently, 48 months after surgery, there has been no local recurrence or metastasis, but continuous strict follow-up will be necessary.