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 Statements on Form S-3 (No. 333-68478 and No. 333-83918) and Form S-8 (No. 33-48380, No. 33-67606, No. 333-103904 and No. 333-124786) of Fred's, Inc. of our reports, relating to the consolidated financial statements, financial statement schedule, and the effectiveness of Fred's, Inc.’s internal control over financial reporting, which appear in this Form 10-K.

/s/BDO USA, LLP

Memphis, Tennessee

April 13, 2017