EXHIBIT 5.1

May 19, 2017

Stage Stores, Inc.

2425 West Loop South

Houston, TX 77027

Re: Stage Stores, Inc. - Registration Statement on Form S-8

Stage Stores 2017 Long-Term Incentive Plan

Ladies and Gentlemen:

We have acted as counsel for Stage Stores, Inc., a Nevada corporation (the “Company”), in connection with the Company’s Registration Statement on Form S-8 (the “Registration Statement”) to be filed with the Securities and Exchange Commission on the date hereof in order to register 1,365,654 shares, $0.01 par value, of the Company’s common stock (the “Common Stock”) under the provisions of the Securities Act of 1933, as amended (the “Act”), and the rules and regulations promulgated thereunder (the “Rules and Regulations”), for issuance and delivery pursuant to awards to be granted under the Stage Stores 2017 Long-Term Incentive Plan (the “Plan”).

In rendering the opinions expressed herein, we have examined, to the extent deemed necessary, originals or copies certified or otherwise identified to our satisfaction, of such documents, corporate records and other instruments as we have deemed necessary or appropriate for the purpose of the opinions, including: (a) the Registration Statement, (b) the Plan, (c) the Company’s Amended and Restated Articles of Incorporation, as currently in effect, (d) the Company’s Amended and Restated Bylaws, as currently in effect, (e) the Company’s Form of Indemnity Agreement, and (f) certain corporate records of the Company, including resolutions adopted by the Company’s Board of Directors (the “Board”) and by the Compensation Committee of the Board.

In rendering the opinions expressed herein, we have also assumed: (i) the genuineness of all signatures, (ii) the legal capacity and competency of all natural persons, (iii) the authenticity of all documents submitted to us as originals and the conformity to the originals of all documents submitted to us as copies, (iv) the correctness and accuracy of all facts set forth in this opinion, and (v) compliance in the future with the terms of the Plan by the Company and its employees, officers, the Board and any committees appointed to administer the Plan.

Based upon and subject to the foregoing and subject to the exceptions, qualifications and limitations set forth below, we are of the opinion that:

1. The Common Stock has been duly authorized; and

2. When issued in accordance with the provisions of the Plan, the Common Stock will be validly issued, fully paid and non-assessable.

May 19, 2017

Stage Stores, Inc.

Registration Statement on Form S-8

Stage Stores 2017 Long-Term Incentive Plan

Page 2

The opinions expressed herein are given as of the date hereof, and we undertake no, and hereby disclaim any, obligation to advise you of any change in any matter set forth herein.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to us therein. In giving this consent, we do not admit that we come within the category of persons whose consent is required under Section 7 of the Act or the Rules and Regulations.

Except in connection with the Registration Statement as aforesaid, no portion of this opinion may be quoted or otherwise used by any person without our prior written consent.

Very truly yours,

/s/ McAfee & Taft, A Professional Corporation

McAfee & Taft A Professional Corporation