Exhibit 23.1

Consent of Independent Registered Public Accounting Firm

Fred’s, Inc.

Memphis, Tennessee

We hereby consent to the incorporation by reference in the Registration Statement on Form S-8 of Fred’s, Inc. of our reports dated April 13, 2017, relating to the consolidated financial statements, the effectiveness of Fred’s, Inc.’s internal control over financial reporting, and schedules of Fred’s, Inc. appearing in the Company’s Annual Report on Form 10-K for the year ended January 28, 2017.

/s/ BDO USA, LLP

Memphis, Tennessee

June 23, 2017