Exhibit 23.1

Consent of Independent Registered Public Accounting Firm

We consent to the incorporation by reference in the Registration Statements on Form S-8 (Registration Statement Nos. 333-173729, 333-167134, 333-167133, 333-151694, 333-135719, 333-126008, 333-116831, 333-84822, 333-34384, 333-58619, 33-86980, and 33-72812) of Books-A-Million, Inc. of our report dated April 19, 2013, with respect to the consolidated financial statements of Books-A-Million, Inc. and Subsidiaries, included in this Annual Report (Form 10-K) for the year ended February 2, 2013.

/s/ Ernst & Young LLP

Birmingham, Alabama

April 19, 2013