Exhibit 5.1

November 18, 2008

Advance Auto Parts, Inc.

5008 Airport Road

Roanoke, Virginia 24012

Re: Registration Statement on Form S-8

Ladies and Gentlemen:

This opinion is furnished in connection with the registration, pursuant to a Registration Statement on Form S-8 under the Securities Act of 1933, as amended (the “Act”), filed with the Securities and Exchange Commission on November 18, 2008 (the “Registration Statement”), of 3,000,000shares (the “Shares”) of common stock, par value $0.0001 per share (the “Common Stock”), of Advance Auto Parts, Inc., a Delaware corporation (the “Company”), reserved for issuance pursuant to the Company’s 2004 Long-Term Incentive Plan (the “Plan”).

We have acted as counsel to the Company in connection with the foregoing Registration Statement. We have examined and relied upon originals or copies of such records, instruments, certificates, memoranda and other documents as we have deemed necessary or advisable for purposes of this opinion and have assumed, without independent inquiry, the accuracy of those documents. 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 further assumed that all options granted or to be granted pursuant to the Plan were or will be validly granted in accordance with the terms of the Plan, that all Shares to be issued upon exercise of such options will be issued in accordance with the terms of such options and the Plan, and that all Shares sold or granted as restricted stock or pursuant to awards of stock appreciation rights, performance awards, deferred stock units or other stock unit awards will be sold or granted in accordance with the terms of the Plan and for legal and sufficient consideration under the Delaware General Corporation Law (the “DGCL”).

We have made such examination of law as we have deemed necessary for the purpose of this opinion.  This opinion is limited solely to the DGCL, as applied by courts located in Delaware, the applicable provisions of the Delaware Constitution and the reported judicial decisions interpreting those laws.

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

1.           Upon the issuance and delivery of the Shares upon the exercise of options granted under the Plan in accordance with the terms of such options and the Plan, and upon the Company’s receipt of the full exercise price therefor, as determined by the Board of Directors of the Company and as specified in the documents governing such grants and the Plan, the Shares will be validly issued, fully paid and nonassessable.

Advance Auto Parts, Inc.

November 18, 2008

Page 2

2.           Upon the issuance and delivery of the Shares pursuant to awards of restricted stock, stock appreciation rights, performance awards, deferred stock units or other stock unit awards granted under the Plan in accordance with the terms of such awards and the Plan, and upon the Company’s receipt of lawful consideration therefor, as determined by the Board of Directors of the Company and as specified in the documents governing such grants and the Plan, the Shares will be validly issued, fully paid, and nonassessable.

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 letter, and we assume no responsibility to inform you of additional or changed facts, or changes in law, of which we may become aware.

We consent to the filing of a copy of this opinion as an exhibit to the Registration Statement.

Very truly yours,

/s/ Bingham McCutchen LLP

Bingham McCutchen LLP