EXHIBIT 5.1

June 29, 2018

Stein Mart, Inc.

1200 Riverplace Blvd.

Jacksonville, Florida 32207

Ladies and Gentlemen:

In our capacity as special counsel for Stein Mart, Inc., a Florida corporation (the “Company”), we have examined the Registration Statement on Form S-8 (the “Registration Statement”), in form as proposed to be filed by the Company with the U.S. Securities and Exchange Commission (the “Commission”) under the provisions of the Securities Act of 1933, as amended (the “Securities Act”), in connection with the offering by the Company of up to 4,100,000 shares of the Company’s common stock, par value $0.01 per share (the “Common Stock”), pursuant to the Stein Mart, Inc. 2018 Omnibus Incentive Plan (the “Plan”), plus up to 4,186,234 shares of Common Stock that are subject to awards that were previously granted under the Stein Mart, Inc. 2001 Omnibus Plan that will become available for issuance under the Plan if such awards expire, terminate or are canceled or forfeited (collectively, the “Shares”).

In connection with rendering the opinion set forth in this opinion letter, we have reviewed the Plan and the originals, or photostatic or certified copies, of such records of the Company and certificates of officers of the Company, certificates of public officials and such other documents as we have deemed relevant and necessary as a basis for the opinion expressed herein.

In our examination, we have assumed the genuineness of all signatures, the legal capacity and competency of all natural persons, the authenticity of all documents submitted to us as originals, the conformity to all original documents of all documents submitted to us as copies and the accuracy and completeness of all information provided to us by the Company.

We have also assumed, without independent investigation, that at the time of the issuance of the Shares: (i) the Registration statement will be effective; (ii) all of the terms and conditions for such issuance set forth in the Plan and any related agreements will have been fully satisfied, waived or discharged; (iii) each award agreement setting forth the terms of each award granted pursuant to the Plan will be consistent with the Plan and will have been duly authorized and validly executed and delivered by the parties thereto; (iv) the issuance of the Shares will continue to be duly and validly authorized on the dates that the Shares are issued pursuant to the terms of the Plan and, upon the issuance of any of the Shares, the total number of shares of Common Stock issued and outstanding, after giving effect to such issuance of such Shares, will not exceed the total number of shares of Common Stock the Company is then authorized to issue under its articles of incorporation; and (v) the legal consideration payable in connection with the issuance of the Shares pursuant to the Plan will not be less than the par value of the Common Stock and will be otherwise proper and sufficient.

Based upon the foregoing and the other matters stated herein, we are of the opinion that, when issued and delivered in accordance with the terms set forth in the Plan and against payment of the consideration therefor, the Shares will be validly issued, fully paid and non-assessable.

This opinion letter is limited to the opinion expressly stated herein, and no other opinions are to be inferred or implied. We render no opinion herein as to matters involving the laws of any jurisdiction other than the State of Florida and the United States of America. This opinion is limited to the current laws of the State of Florida and the current federal laws of the United States, and to the facts as they exist on the date hereof. We assume no obligation to revise or supplement our opinion should the present laws, or the interpretations thereof, be changed in respect of any circumstances or events that occur subsequent to the date hereof.

We hereby consent to the filing of this opinion with the Commission as an exhibit to the above referenced Registration Statement. In giving this consent, we do not hereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission promulgated thereunder.

Very truly yours,

/s/ BRADLEY ARANT BOULT CUMMINGS LLP