Exhibit 5.1

	160 MADISON AVENUE SUITE 2000 MEMPHIS, TENNESSEE 38103
	PHONE:          901.577.2330
	FAX:               901.577.0769
	www.bakerdonelson.com

June 23, 2017

Board of Directors

Fred’s, Inc.

4300 New Getwell Rd.

Memphis, TN 38118

Ladies and Gentlemen:

We have acted as counsel to Fred’s, Inc., a Tennessee corporation (the “Company”), in connection with the preparation and filing with the Securities and Exchange Commission (the “Commission”) of the Company’s registration statement on Form S-8 (the “Registration Statement”) under the Securities Act of 1933, as amended (the “Securities Act”), on or about the date hereof relating to 2,610,901 shares of Class A common stock, no par value, of the Company (the “Shares”), which are issuable under the Fred’s, Inc. 2017 Long-Term Incentive Plan (as amended, the “Plan”).  In connection therewith, we have examined, among other things, such records and documents as we have deemed necessary to express the opinions hereinafter set forth.

We have assumed the genuineness and authenticity of all documents submitted to us as originals, and the conformity to originals of all documents where due execution and delivery are a prerequisite to the effectiveness thereof. As to certain factual matters, we have relied upon representations of officers of the Company and have not sought to independently verify such matters.

Based upon the foregoing, we are of the opinion that:

(1)The Company is a duly organized and legally existing corporation under the laws of the State of Tennessee.

(2)The Shares that may be issued and sold from time to time in accordance with the Plan will, when issued, sold and paid for in accordance with the Plan, be validly issued, fully paid and non-assessable.

The opinions provided above are, with your concurrence, subject to the following exceptions, limitations and qualifications: (i) the effect of bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium or other similar laws relating to or affecting the rights and remedies of creditors (including, without limitation, the effect of statutory or other laws regarding preferential transferees); (ii) the effect of general equitable principles (including, without limitation, concepts of materiality, reasonableness, good faith and fair dealing), regardless of whether considered in a proceeding at law or in equity, and the discretion of the court before which any proceeding therefor may be brought; (iii) the unenforceability under certain circumstances under law or court decisions of provisions providing for the indemnification of or contribution to a party with respect to a liability where such indemnification or contribution is contrary to public policy; and (iv) the unenforceability of any provision requiring the payment of attorneys’ fees, where such payment is contrary to law or public policy.

Our examination of matters of law in connection with the opinions expressed herein has been limited to, and accordingly our opinions expressed herein are limited to, the laws of the State of Tennessee. We express no opinion with respect to the laws of any other jurisdiction.

Board of Directors

June 23, 2017

This opinion is given as of the date hereof, and we assume no obligation to advise you after the date hereof of facts or circumstances that come to our attention or changes in law that occur which could affect the opinions contained herein.

We consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference of this firm included therein.  In giving our consent, we do not admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations thereunder.

Very truly yours,
BAKER, DONELSON, BEARMAN, CALDWELL & BERKOWITZ, P.C.
By:	/s/ Samuel D. Chafetz
	Samuel D. Chafetz, Authorized Representative