Leiomyoma of deep soft tissue is a very rare tumor, which is sometimes confused with leiomyosarcoma, histopathologically. We describe a case of palisaded and Verocay-body prominent leiomyoma of deep soft tissue. The lesion was characterized by areas of nuclear palisading with Verocay-body like formation in addition to the features of leiomyoma.