Plexiform fibromyxoma is a rare and distinctive benign mesenchymal neoplasm that occurs in the gastric antrum. This tumor has a potential for misdiagnosis as gastrointestinal stromal tumor (GIST). It causes mucosa and vascular ulcerations without advancement of the tumor. Cytological bland spindle cells within a variably myxoid stroma characterize the histology of the tumor. We report the case of a 41-year-old African Tanzanian lady who presented with melena and recurrent anemia. Endoscopy and imaging studies revealed antral mass with initial suspicion of a GIST. However, immunohistochemically it turned to be a plexiform fibromyxoma. Follow-up evaluation 12 months after surgery revealed no evidence of recurrence or metastasis. This is a very uncommon tumor, which, to our knowledge, has been reported only once in Africa. The clinicians need to be aware of this rare occurrence to avoid misdiagnosis as GIST tumor.