AS FILED WITH THE SECURITIES AND EXCHANGE COMMISSION ON JUNE 24, 2004
                                                      REGISTRATION NO. 333-[___]

================================================================================

                       SECURITIES AND EXCHANGE COMMISSION
                             Washington, D.C. 20549

                             -----------------------

                                    FORM S-8
                             REGISTRATION STATEMENT
                                      Under
                           THE SECURITIES ACT OF 1933

                             -----------------------

                              BOOKS-A-MILLION, INC.
             (Exact name of registrant as specified in its charter)

                DELAWARE                             63-0798460
     (State or other jurisdiction of              (I.R.S. Employer
     incorporation or organization)             Identification No.)

                               402 INDUSTRIAL LANE
                               BIRMINGHAM, ALABAMA
                                 (205) 942-3737

  (Address, including zip code, and telephone number, including area code, of
                   registrant's principal executive offices)

                              --------------------

                 BOOKS-A-MILLION, INC. EXECUTIVE INCENTIVE PLAN
  BOOKS-A-MILLION, INC. 1999 AMENDED AND RESTATED EMPLOYEE STOCK PURCHASE PLAN

                            (Full title of the plan)

                              --------------------

                                SANDRA B. COCHRAN
                      PRESIDENT AND CHIEF EXECUTIVE OFFICER
                              BOOKS-A-MILLION, INC.
                               402 INDUSTRIAL LANE
                               BIRMINGHAM, ALABAMA
                                 (205) 942-3737

 (Name, address, including zip code, and telephone number, including area code,
                              of agent for service)

                              --------------------
                                   Copies to:

                            STEVEN DELLA ROCCA, ESQ.
                              LATHAM & WATKINS LLP
                          885 THIRD AVENUE, SUITE 1000
                            NEW YORK, NEW YORK 10022
                                 (212) 906-1200


                         CALCULATION OF REGISTRATION FEE




                                                         PROPOSED MAXIMUM    PROPOSED MAXIMUM
TITLE OF EACH CLASS OF SECURITIES       AMOUNT TO BE    OFFERING PRICE PER      AGGREGATE
         TO BE REGISTERED              REGISTERED(1)         SHARE(2)         OFFERING PRICE       AMOUNT OF REGISTRATION FEE
-------------------------------------------------------------------------------------------------------------------------------
                                                                                       
Common Stock, par value $0.01
per share.....................            300,000             $5.92             $1,776,000                  $225.02


(1)      Represents (a) 100,000 shares that may be acquired under the
         Books-A-Million, Inc. Executive Incentive Plan ("EIP") and (b) 200,000
         shares that may be acquired under the Books-A-Million, Inc. 1999
         Amended and Restated Employee Stock Purchase Plan ("ESPP"). The ESPP
         authorizes the issuance of up to a maximum of 400,000 shares of common
         stock of Books-A-Million, Inc. (the "Company"). Pursuant to Rule 416 of
         the Securities Act of 1933, as amended (the "Securities Act"),
         additional shares of common stock, par value $.01 per share ("Common
         Stock") of the Company which become issuable to prevent dilution from
         any future stock split, stock dividend or similar transaction are also
         being registered.

(2)      For purposes of computing the registration fee only. Pursuant to Rule
         457(h) of the Securities Act, the Proposed Maximum Offering Price Per
         Share is based upon the average of the high and low trading prices
         ($5.92) of the Common Stock as reported by the National Association of
         Securities Dealers' Automated Quotation Service on June 18, 2004.

(3)      In addition, pursuant to Rule 416(c) under the Securities Act, this
         Registration Statement also covers an indeterminate amount of interests
         to be offered pursuant to the EIP and the ESPP.



                                     PART I

Item 1.           Plan Information

                  Not required to be filed with this Registration Statement.

Item 2.           Registration Information and Employee Plan Annual Information

                  Not required to be filed with this Registration Statement.

                                     PART II


I.       INCORPORATION OF DOCUMENTS BY REFERENCE.

         The following documents, which have been filed with the Securities and
Exchange Commission pursuant to Securities Exchange Act of 1934, as amended (the
"Exchange Act"), are hereby incorporated by reference in, and shall be deemed to
be a part of, this Registration Statement:

         A.       The Company's Quarterly Report on Form 10-Q for the quarter
                  ended May 1, 2004.

         B.       The Company's Annual Report on Form 10-K for the year ended
                  January 31, 2004.

         C.       The Company's Quarterly Report on Form 10-Q for the quarter
                  ended May 3, 2003.

         D.       The Company's Quarterly Report on Form 10-Q for the quarter
                  ended August 2, 2003.

         E.       The Company's Quarterly Report on Form 10-Q for the quarter
                  ended November 1, 2003.

         F.       The description of the Company's Common Stock contained in the
                  Company's Registration Statement on S-1 (File No. 33-52256),
                  including any amendment or report filed for the purposes of
                  updating such description.

         All documents filed by the Company pursuant to Sections 13(a), 13(c),
14 and 15(d) of the Exchange Act prior to the filing of a post-effective
amendment which indicates that all securities offered have been sold or which
deregisters all securities then remaining unsold are incorporated by reference
in this Registration Statement. Any statement contained in a document
incorporated or deemed to be incorporated by reference herein shall be deemed to
be modified or superseded for purposes of this Registration Statement to the
extent that a statement contained herein, or in any subsequently filed document
which also is or is deemed to be incorporated by reference herein, modifies or
supersedes such statement. Any such statement so modified or superseded shall
not be deemed, except as so modified or superseded, to constitute part of this
Registration Statement.


                                       2



II.      DESCRIPTION OF SECURITIES.

         Not Applicable.

III.     INTERESTS OF NAMED EXPERTS AND COUNSEL.

         Not Applicable.

IV.      INDEMNIFICATION OF DIRECTORS AND OFFICERS.

         Section 145 of the General Corporation Law of Delaware provides that a
corporation may indemnify its directors and officers against civil and criminal
liabilities. Directors and officers may be indemnified against expenses if they
acted in good faith an in a manner reasonably believed to be in or not opposed
to the best interests of the corporation and, with respect to any criminal
action, if they had no reasonable cause to believe their conduct was unlawful. A
director or officer may be indemnified against expenses incurred in connection
with a derivative suit if he acted in good faith and in a manner reasonably
believed to be in or not opposed to the best interests of the corporation,
except that no indemnification may be made without court approval if such person
was adjudged liable for negligence or misconduct in the performance of his or
her duty to the corporation. The statutory indemnification is not exclusive of
any rights provided by and by-law, agreement, vote of shareholders or
disinterested directors or otherwise.

         Article X of the Company's Certificate of Incorporation sets forth the
extent to which the Company's directors and officers may be indemnified against
liabilities and other monetary expenses which they may incur while serving in
such capacities. Such indemnification will be provided to the full extent
permitted and in the manner required by the General Corporation Law of Delaware.
Article VI of the Company's By-laws also provides that the directors and
officers of the Company will be indemnified against any losses incurred in
connection with any threatened, pending or completed action, suit or proceeding,
whether civil, criminal, administrative or investigative, by reason of the fact
that he is or was a director or officer of the Company or served with another
corporation, partnership, joint venture, trust or other enterprise at the
request of the Company and will provide advances, for expenses incurred in
defending any such action, suit or proceeding, upon receipt of an undertaking by
or on behalf of such officer or director to repay such advances, if it is
ultimately determined that he is not entitled to indemnification by the Company.

V.       EXEMPTION FROM REGISTRATION CLAIMED.

         Not Applicable.

VI.      EXHIBITS.

         A list of exhibits included as part of this Registration Statement is
set forth on the Exhibit Index appearing elsewhere herein and is incorporated
herein by reference.


                                       3


VII.     UNDERTAKINGS.

         1.       The undersigned Registrant hereby undertakes:

                  a.       To file, during any period in which offers or sales
                           are being made, a post-effective amendment to this
                           Registration Statement:

                           (1)      To include any prospectus required by
                                    Section 10(a)(3) of the Securities Act;

                           (2)      To reflect in the prospectus any facts or
                                    events arising after the effective date of
                                    this Registration Statement (or the most
                                    recent post-effective amendment thereof)
                                    which, individually or in the aggregate,
                                    represent a fundamental change in the
                                    information set forth in the Registration
                                    Statement;

                           (3)      To include any material information with
                                    respect to the plan of distribution not
                                    previously disclosed in the Registration
                                    Statement or any material change to such
                                    information in the Registration Statement;

                  provided, however, that paragraphs (a)(1)(i) and (a)(1)(ii)
                  shall not apply to information contained in periodic reports
                  filed by the Registrant pursuant to Section 13 or Section
                  15(d) of the Exchange Act that are incorporated by reference
                  in this Registration Statement.

                  b.       That, for the purpose of determining any liability
                           under the Act, each such post-effective amendment
                           shall be deemed to be a new registration statement
                           relating to the securities offered therein, and the
                           offering of such securities at that time shall be
                           deemed to be the initial bona fide offering thereof.

                  c.       To remove from registration by means of a
                           post-effective amendment any of the securities being
                           registered that remain unsold at the termination of
                           the offering.

         2.       The undersigned Registrant hereby undertakes that, for
                  purposes of determining any liability under the Securities
                  Act, each filing of the Registrant's Annual Report pursuant to
                  section 13(a) or 15(d) of the Exchange Act (and, where
                  applicable, each filing of an employee benefit plan's annual
                  report pursuant to Section 15(d) of the Exchange Act) that is
                  incorporated by reference in the registration statement shall
                  be deemed to be a new registration statement relating to the
                  securities offered therein, and the offering of such
                  securities at that time shall be deemed to be the initial bona
                  fide offering thereof.


                                       4


         3.       Insofar as indemnification for liabilities arising under the
                  Securities Act may be permitted to directors, officers and
                  controlling persons of the Registrant pursuant to the
                  foregoing provisions, or otherwise, the Registrant has been
                  advised that in the opinion of the Securities and Exchange
                  Commission such indemnification is against public policy as
                  expressed in the Securities Act and is, therefore,
                  unenforceable. In the event that a claim for indemnification
                  against such liabilities (other than the payment by the
                  Registrant of expenses incurred or paid by a director, officer
                  or controlling person of the Registrant in the successful
                  defense of any action, suit or proceeding) is asserted by such
                  director, officer or controlling person in connection with the
                  securities being registered, the Registrant will, unless in
                  the opinion of its counsel the matter has been settled by
                  controlling precedent, submit to a court of appropriate
                  jurisdiction the question whether such indemnification by it
                  is against public policy as expressed in the Securities Act
                  and will be governed by the final adjudication of such issue.


                                       5


                                   SIGNATURES

         Pursuant to the requirements of the Securities Act, the Registrant
certifies that it has reasonable grounds to believe that it meets all of the
requirements for filing on Form S-8 and has duly caused this Registration
Statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in the City of Birmingham, State of Alabama, on June 24, 2004.

                                  BOOKS-A-MILLION, INC.


                              By       /s/ Sandra B. Cochran
                                    --------------------------------------------
                                    Name:  Sandra B. Cochran
                                    Title: President and Chief Executive Officer

                                POWER OF ATTORNEY

         Each of the undersigned officers and directors of the Company hereby
severally constitutes and appoints Clyde B. Anderson and Sandra B. Cochran as
the undersigned's true and lawful attorney-in-fact and agent, with full power of
substitution and resubstitution, for the undersigned and in the undersigned's
name, place and stead, in any and all capacities (unless revoked in writing) to
sign this Registration Statement on Form S-8, and any and all amendments
thereto, including any post-effective amendments as well as any related
registration statement (or amendment thereto) filed in reliance upon Rule 462(b)
under the Securities Act, as amended, and to file the same, with all exhibits
thereto, and other documents in connection therewith, with the Securities and
Exchange Commission, granting to such attorney-in-fact and agent full power and
authority to do and perform each and every act and thing requisite or necessary
to be done in connection therewith, as fully to all intents and purposes as the
undersigned might and could do in person hereby ratifying and confirming all
that said attorney-in-fact and agent or her substitute or substitutes, may
lawfully do or cause to be done by virtue thereof.


                                      S-1



         Pursuant to the requirements of the Securities Act, this Registration
Statement has been signed by the following persons in the capacities and on the
date indicated.




           Signature                              Title                              Date
           ---------                              -----                              ----
                                                                          

  /s/ Sandra B. Cochran                Chief Executive Officer                  June 24, 2004
---------------------------------
      Sandra B. Cochran

   /s/ Richard S. Wallington           Chief Financial Officer                  June 24, 2004
---------------------------------      (Principal Financial and
       Richard S. Wallington           Accounting Officer)

     /s/ Clyde B. Anderson             Director and Principal Executive         June 24, 2004
---------------------------------      Officer
         Clyde B. Anderson

   /s/ Charles C. Anderson                        Director                      June 24, 2004
---------------------------------
       Charles C. Anderson

     /s/ Terry C. Anderson                        Director                      June 24, 2004
---------------------------------
         Terry C. Anderson

    /s/ Ronald G. Bruno                           Director                      June 24, 2004
---------------------------------
        Ronald G. Bruno

   /s/ J. Barry Mason                             Director                      June 24, 2004
---------------------------------
       J. Barry Mason

   /s/ William H. Rogers, Jr.                     Director                      June 24, 2004
---------------------------------
       William H. Rogers, Jr.


          Pursuant to the requirements of the Securities Act of 1933, as
amended, the Books-A-Million, Inc. 1999 Amended and Restated Employee Stock
Purchase Plan has duly caused this Registration Statement to be signed on its
behalf by the undersigned, thereunto duly authorized, in the City of Birmingham,
State of Alabama, on June 24, 2004.

                                    BOOKS-A-MILLION, INC. 1999 AMENDED AND
                                    RESTATED EMPLOYEE STOCK PURCHASE PLAN

                                    By:  Compensation Committee of the Board of
                                         Directors -- Plan Administrator

                                         By:   /s/ Ronald G. Bruno
                                             -----------------------------------
                                             Ronald G. Bruno

                                         By: /s/ J. Barry Mason
                                             -----------------------------------
                                             J. Barry Mason

                                         By: /s/ William H. Rogers, Jr.
                                             -----------------------------------
                                             William H. Rogers, Jr.


                                      S-2



         Pursuant to the requirements of the Securities Act of 1933, as amended,
the Books-A-Million Executive Incentive Plan has duly caused this Registration
Statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in the City of Birmingham, State of Alabama, on June 24, 2004.


                                    BOOKS-A-MILLION EXECUTIVE INCENTIVE PLAN


                                    By:  Compensation Committee of the Board of
                                         Directors -- Plan Administrator


                                         By:     /s/ Ronald G. Bruno
                                               --------------------------------
                                               Ronald G. Bruno

                                         By:   /s/ J. Barry Mason
                                               --------------------------------
                                               J. Barry Mason

                                         By:   /s/ William H. Rogers, Jr.
                                               --------------------------------
                                               William H. Rogers, Jr.



                                      S-3



                                INDEX TO EXHIBITS



        EXHIBIT                             DESCRIPTION
        -------                             -----------
               

         4.1      Certificate of Incorporation of the Company (incorporated
                  herein by reference to the exhibits to the Company's
                  Registration Statement on Form S-1, File No. 33-52256).

         4.2      By-Laws of the Company (incorporated by reference to the
                  exhibits to the Company's Registration Statement on Form S-1,
                  File No. 33-52256).

         4.3      Specimen Certificate of Common Stock (incorporated herein by
                  reference to the exhibits to the Company's Registration
                  Statement on Form S-1, File No. 33-52256).

         4.4      The Books-A-Million, Inc. 1999 Amended and Restated Employee
                  Stock Purchase Plan (incorporated herein by reference to
                  Appendix A to the Company's Proxy Statement, File No.
                  000-20664, for the Annual Meeting of the Company's
                  Stockholders held June 6, 1999).

         4.5      The Books-A-Million, Inc. Executive Incentive Plan and the
                  first amendment thereto.

         4.6      First Amendment to the Books-A-Million, Inc. 1999 Amended and
                  Restated Employee Stock Purchase Plan.

         5.1      Opinion of Counsel.

         23.1     Independent Auditors' Consent.

         23.2     Consent of Counsel (included in Exhibit 5.1).

         24.1     Powers of Attorney (included on the signature pages to the
                  Registration Statement).