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 2,000,000 shares (the “Shares”) of the Company’s common stock, par value $0.01 per share (the “Common Stock”), pursuant to the Stein Mart, Inc. Employee Stock Purchase Plan (the “ESPP”).

In connection with rendering the opinion set forth in this opinion letter, we have reviewed the ESPP 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. In rendering the opinion set forth below, we have relied without investigation on all information provided to us by the Company and have assumed that there are no agreements or understandings between or among the Company and any participants in the ESPP that would expand, modify or otherwise affect the terms of the ESPP or the respective rights or obligations of the participants thereunder.

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 ESPP and any related agreements will have been fully satisfied, waived or discharged; (iii) 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 ESPP 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 (iv) the legal consideration payable in connection with the issuance of the Shares pursuant to the ESPP 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 ESPP 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