Exhibit 10.45

SUPPLEMENT No. 1 (this “Supplement”) dated as of January 31, 2014, to the Guarantee Agreement dated as of December 5, 2013 (the “Guarantee Agreement”), among ADVANCE AUTO PARTS, INC., a Delaware corporation (“Parent”), ADVANCE STORES COMPANY, INCORPORATED, a Virginia corporation (the “Borrower”), the subsidiaries of the Borrower from time to time party thereto (the “Subsidiary Guarantors” and, together with Parent, the “Guarantors”) and JPMORGAN CHASE BANK, N.A. (“JPMCB”), as administrative agent for the Lenders.

A. Reference is made to the Credit Agreement dated as of December 5, 2013 (as amended, restated, amended and restated, supplemented or otherwise modified from time to time, the “Credit Agreement”), among Parent, the Borrower, the lenders from time to time party thereto (the “Lenders”) and JPMCB, as administrative agent (in such capacity, the “Administrative Agent”) for the Lenders.

B. Capitalized terms used herein and not otherwise defined herein shall have the meanings assigned to such terms in the Credit Agreement and the Guarantee Agreement, as applicable.

C. The Borrower and the Guarantors have entered into the Guarantee Agreement in order to induce the Lenders to make Loans and the Issuing Banks to issue Letters of Credit. Pursuant to the definition of the term “Guarantee Requirement” and Section 5.10 of the Credit Agreement, the Acquired Company, its Subsidiaries that constitute Material Subsidiaries as of the Acquisition Date and each other Material Subsidiary that was not in existence or not a Material Subsidiary on the Effective Date is required to enter into the Guarantee Agreement as a Subsidiary Guarantor no more than 30 days after the Acquisition Date or the date of determination (in accordance with the provisions of the definition of “Material Subsidiary” in the Credit Agreement) that such Subsidiary has become (or is deemed to be) a Material Subsidiary, as applicable. Section 20 of the Guarantee Agreement provides that such Material Subsidiaries and other additional Subsidiaries may become Subsidiary Guarantors under the Guarantee Agreement by execution and delivery of an instrument in the form of this Supplement. Each undersigned Subsidiary (each, a “New Guarantor”) is executing this Supplement in accordance with the requirements of the Credit Agreement and the Guarantee Agreement to become a Subsidiary Guarantor under the Guarantee Agreement in order to induce the Lenders to make additional Loans and the Issuing Banks to issue additional Letters of Credit and as consideration for Loans previously made and Letters of Credit previously issued.

Accordingly, the Administrative Agent and each New Guarantor agree as follows:

In accordance with Section 20 of the Guarantee Agreement, each New Guarantor by its signature below becomes a Guarantor under the Guarantee Agreement with the same force and effect as if originally named therein as a Guarantor and each New Guarantor hereby (a) agrees to be bound by and comply with all the terms and provisions of the Guarantee Agreement applicable to it as a Guarantor thereunder and to perform all of its obligations as a Guarantor thereunder (b) represents and warrants that the representations and warranties relating to it contained in the Credit Agreement are true and correct in all material respects on and as of the date hereof. Each reference to a “Guarantor” in the Guarantee Agreement shall be deemed to include each New Guarantor.

Each New Guarantor represents and warrants to the Administrative Agent, the other Lenders and the Issuing Banks that this Supplement has been duly executed and delivered by the New Guarantor and constitutes a legal, valid and binding obligation of such New Guarantor, enforceable in accordance with its terms, subject to applicable bankruptcy, insolvency, reorganization, moratorium or other laws affecting creditors’ rights generally and subject to general principles of equity, regardless of whether considered in a proceeding in equity or at law.

This Supplement may be executed in counterparts, each of which shall constitute an original, but all of which when taken together shall constitute a single contract. This Supplement shall become effective when the Administrative Agent shall have received counterparts of this Supplement that, when taken together, bear the signatures of each New Guarantor and the Administrative Agent. Delivery of an executed signature page to this Supplement by facsimile or other electronic methods of transmission shall be as effective as delivery of a manually executed counterpart of this Supplement.

Except as expressly supplemented hereby, the Guarantee Agreement shall remain in full force and effect.

THIS SUPPLEMENT SHALL BE GOVERNED BY, AND CONSTRUED IN ACCORDANCE WITH, THE LAWS OF THE STATE OF NEW YORK.

In case any one or more of the provisions contained in this Supplement should be held invalid, illegal or unenforceable in any respect, the validity, legality and enforceability of the remaining provisions contained herein and in the Guarantee Agreement shall not in any way be affected or impaired thereby (it being understood that the invalidity of a particular provision hereof in a particular jurisdiction shall not in and of itself affect the validity of such provision in any other jurisdiction).

All communications and notices hereunder shall be in writing and given as provided in Section 13 of the Guarantee Agreement. All communications and notices hereunder to a New Guarantor shall be given to it in care of the Borrower.

Each New Guarantor agrees to reimburse the Administrative Agent for its out-of-pocket expenses in connection with this Supplement in accordance with Section 9.03 of the Credit Agreement.

IN WITNESS WHEREOF, the New Guarantor and the Administrative Agent have duly executed this Supplement to the Guarantee Agreement as of the day and year first above written.

WORLDPAC, Inc.

WORLDPAC Puerto Rico, LLC

General Parts, Inc.

Golden State Supply LLC

Worldwide Auto Parts

Straus-Frank Enterprises LLC

General Parts Distribution LLC

GPI Technologies, LLC

CQ Sourcing, Inc.

General Parts International, Inc.

Lee Holdings NC, Inc.

Valley Master Partnership LLC

Western Auto of St. Thomas, Inc.

by

Name: Michael A. Norona

Title: Chief Financial Officer

JPMORGAN CHASE BANK, N.A., as Administrative Agent,

by

Name:

Title: