EXHIBIT 5.1

May 21, 2004

Advance Auto Parts, Inc.
5673 Airport Road
Roanoke, Virginia 24012

Re: Advance Auto Parts, Inc. – Registration Statement on Form S-8

Dear Sir or Madam:

        You have requested our opinion with respect to certain matters in connection with the filing by Advance Auto Parts, Inc. (the “Company”) of a Registration Statement on Form S-8 (the “Registration Statement”) with the Securities and Exchange Commission on or about May 21, 2004. The Registration Statement covers (i) the registration of 5,746,847 shares (the “Shares”) of Common Stock, par value $0.0001 per share (the “Common Stock”), of the Company, issuable upon the exercise of stock options or pursuant to other stock-based awards to be issued by the Company pursuant to the terms of the Company’s 2004 Long-Term Incentive Plan (the “Plan”), and (ii) the registration of deferred compensation obligations (the “Obligations”) to pay deferred compensation in the future in accordance with the terms of the Company’s Deferred Stock Unit Plan for Non-Employee Directors and Selected Executives (the “Deferred Plan”).

        In connection with this opinion, we have examined the following documents:

                    (a)        the Plan;

                    (b)        the Deferred Plan;

                    (c)        copies of the Company’s Restated Certificate of Incorporation, as amended, and Bylaws; and

                    (d)        a certificate executed by an officer of the Company, certifying as to, and attaching copies of, the Company’s Restated Certificate of Incorporation, as amended, Bylaws, the Plan, the Deferred Plan, certain resolutions of the Company’s Board of Directors approving the Plan and the Deferred Plan, reserving 5,746,847 shares of Common Stock for issuance under the Plan and authorizing the filing of the Registration Statement.

        This opinion is based entirely on our examination of the documents listed in the preceding paragraph and we have made no other documentary review or investigation of any kind whatsoever for purposes of this opinion. In that examination, we have assumed the genuineness of all signatures, the conformity to the originals of all documents reviewed by us as copies, the authenticity and completeness of all original documents reviewed by us in original or copy form and the legal competence of each individual executing such documents.

        We have assumed that the consideration for all Shares duly granted and issued under the Plan will be greater than or equal to the par value per share of the Shares.

        We have further assumed that all applicable requirements of state laws regulating the sale of securities will have been duly satisfied.

        This opinion is limited solely to the Delaware General Corporation Law, as applied by courts located in the State of Delaware, the applicable provisions of the State of Delaware Constitution and the reported judicial decisions interpreting those laws.

        Based upon and subject to the foregoing, we are of the opinion that:

                    (1)        the Shares when duly granted and issued in accordance with the Plan or issued upon exercise of options duly granted in accordance with the Plan, for the consideration described in such options, will be validly issued, fully paid, and nonassessable;

                    (2)        the Obligations, when established pursuant to the Deferred Plan, will be valid and binding obligations of the Company, enforceable against the Company in accordance with the Deferred Plan’s terms, except as the enforceability of the Obligations may be limited by bankruptcy, insolvency, reorganization, fraudulent transfer, fraudulent conveyance, voidable preference, or any laws, regulations or judicial opinions relating to or affecting creditors’ rights or by equitable principles; and

                    (3)        the provisions of the Deferred Plan comply with the applicable provisions of the Employee Retirement Income Security Act of 1974, as amended (“ERISA”). However, without limiting the preceding sentence, we express no opinion as to whether the individuals who are eligible to participate in the Deferred Plan constitute a select group of management or highly compensated employees, or whether the Deferred Plan will be considered “funded” for purposes of ERISA, which are factual determinations.

        We express no opinion as to the effect of events occurring, circumstances arising, or changes of law becoming effective or occurring, after the date hereof

on the matters addressed in this opinion and we assume no responsibility to inform you of additional or changed facts or law of which we may become aware.

        This opinion is rendered solely in connection with the registration of the Shares of Common Stock and the Obligations under the Registration Statement.

        We hereby consent to the filing of this opinion as an exhibit to the Registration Statement. In giving such consent, we do not thereby admit that we are within the category of persons whose consent is required by Section 7 of the Securities Act of 1933, as amended, and the rules and regulations promulgated thereunder.

Sincerely yours,

BINGHAM McCUTCHEN LLP