FIRST SUPPLEMENT TO THE PLEDGE AGREEMENT AMONG

Exhibit 4.13

FIRST SUPPLEMENT

TO THE

PLEDGE AGREEMENT

AMONG

ALBERTSON’S LLC,

NEW ALBERTSON’S, INC.

AND

U.S. BANK TRUST NATIONAL ASSOCIATION,

AS COLLATERAL AGENT, CUSTODIAL AGENT,

SECURITIES INTERMEDIARY,

AND PURCHASE CONTRACT AGENT

1

THIS FIRST SUPPLEMENT TO THE PLEDGE AGREEMENT, dated as of June 1, 2006 (this “Supplemental Agreement”), among Albertson’s LLC, a Delaware limited liability company (the “Company”) and formerly a Delaware corporation known as Albertson’s, Inc. (“Albertson’s”), New Albertson’s, Inc., a Delaware corporation formerly known as New Aloha Corporation (“New Albertson’s”), and U.S. Bank Trust National Association, acting as collateral agent (in such capacity, the “Collateral Agent”), as custodial agent (in such capacity, the “Custodial Agent”), as securities intermediary with respect to the Collateral Account (in such capacity, the “Securities Intermediary”), in each case pursuant to the Pledge Agreement (as hereafter referred to), and as purchase contract agent and as attorney-in-fact of the Holders from time to time of the Units (in such capacity, the “Purchase Contract Agent”, and in all such capacities collectively, the “Agents”) pursuant to the Purchase Contract Agreement (as hereafter referred to),

WHEREAS, Albertson’s and the Agents executed and delivered a Pledge Agreement, dated as of May 7, 2004 (the “Pledge Agreement”);

WHEREAS, Albertson’s and the Purchase Contract Agent executed and delivered a Purchase Contract Agreement, dated as of May 7, 2004, as supplemented (the “Purchase Contract Agreement”), to provide for the execution and delivery of the Purchase Contracts and Certificates related to the Corporate Units and the Treasury Units (collectively, the “Units”);

WHEREAS, Albertson’s has filed a Certificate of Conversion with the Secretary of State of the state of Delaware, pursuant to which it has converted from a Delaware corporation into the Company (the “Conversion”);

WHEREAS, as a result of the Conversion and without need for any further action, the Pledge Agreement became the continuing obligation of the Company;

WHEREAS, New Albertson’s has entered into that Purchase and Separation Agreement, dated as of January 22, 2006, by and among Albertson’s, New Albertson’s, SUPERVALU INC., and AB Acquisition LLC, as amended (the “Separation Agreement”);

WHEREAS, pursuant to the Separation Agreement, the Company shall have transferred certain assets and property to New Albertson’s (such transfer, the “Separation”); and

WHEREAS, as a condition to the Separation, Section 901 of the Purchase Contract Agreement requires, among other things, that New Albertson’s execute and deliver one or more supplemental agreements to expressly assume all the obligations of the Company under the Purchase Contracts, the Purchase Contract Agreement, the Pledge Agreement, the Indenture (including any supplement thereto) and the Remarketing Agreement

WHEREAS, Section 10.01(a) of the Pledge Agreement authorizes the Company and the Agent to enter into a supplemental agreement without the consent of any Holders to evidence the succession of another Person to the Company, and the assumption of such Person of the covenants of the Company in the Pledge Agreement

WHEREAS, New Albertson’s and the Company desire to enter into an amendment pursuant to the terms of Section 10.01(a) of the Pledge Agreement;

1

WHEREAS, New Albertson’s and the Company have requested that the Agents execute and deliver this Supplemental Agreement; and

NOW THEREFORE, in consideration of their mutual promises, New Albertson’s and the Company covenant and agree with the Agents as follows:

ARTICLE I

DEFINITIONS

Section 1.1 Definition of Terms. Unless the context otherwise requires:

(a) a term defined in the Pledge Agreement has the same meaning when used in this Supplemental Agreement;

(b) a term defined anywhere in this Supplemental Agreement has the same meaning throughout;

(c) the singular includes the plural and vice versa; and

(d) headings are for convenience of reference only and do not affect interpretation.

ARTICLE II

REPRESENTATIONS AND WARRANTIES

Section 2.1 Each of New Albertson’s and the Company represents and warrants that the Separation constitutes the transfer of all or substantially all the Company’s properties and assets to New Albertson’s.

ARTICLE III

ASSUMPTION OF OBLIGATIONS

Section 3.1 Assumption. New Albertson’s hereby expressly assumes all the obligations of the Company under the Pledge Agreement.

Section 3.2 Acceptance by Agents. The Agents accept this Supplemental Agreement and agree to execute their duties and responsibilities as hereby supplemented upon the terms and conditions set forth in the Pledge Agreement, including without limitation the terms and provisions defining and limiting the liabilities and responsibilities of the Agents, which terms and provisions shall in like manner define and limit its liabilities and responsibilities in the performance of its duties created by the Pledge Agreement as hereby supplemented; and without limiting the generality of the foregoing, New Albertson’s and the Company affirm their rights and responsibilities with respect to the Agents under Section 9.08 of the Pledge Agreement.

2

ARTICLE IV

SUCCESSION

Section 4.1 Succession. Upon the consummation of the Separation (the time at which such consummation occurs, the “Succession Time”), New Albertson’s shall succeed to the Company under the Pledge Agreement, with the same effect as if New Albertson’s had been named as “the Company” in the Pledge Agreement.

ARTICLE V

CONCERNING COMMON STOCK

Section 5.1 References to Common Stock. From and after the date hereof, references in the Pledge Agreement to the delivery, issuance or purchase of the Common Stock of the Company in connection with the settlement of Purchase Contracts shall be deemed to refer to the delivery, issuance or purchase of any such securities, cash or property that the Holders of Units are entitled to receive upon settlement of such Purchase Contracts taking into account, among other things, any adjustment of the Settlement Rate under the Purchase Contract pursuant to Section 5.04(b)(i) of the Purchase Contract Agreement.

ARTICLE VI

MISCELLANEOUS

Section 6.1 Ratification of Pledge Agreement. The Pledge Agreement, as supplemented by this Supplemental Agreement, is in all respects ratified and confirmed, and this Supplemental Agreement shall be deemed part of the Pledge Agreement in the manner and to the extent herein and therein provided.

Section 6.2 Effectiveness. This Supplemental Agreement shall become a legally effective and binding instrument upon the execution and delivery hereof by all parties hereto.

Section 6.3 Pledge Agreement. Except as supplemented hereby, all provisions in the Pledge Agreement shall remain in full force and effect.

Section 6.4 Third Party Rights. Nothing in this Supplemental Agreement or the Units, express or implied, shall give to any Person, other than the parties hereto and thereto and their successors hereunder and thereunder and the Holders of the Units, any benefit of any legal or equitable right, remedy or claim under the Pledge Agreement, this Supplemental Agreement or the Units.

Section 6.5 Successors. All agreements of the Company and New Albertson’s in this Supplemental Agreement shall bind their respective successors and assigns, whether so expressed or not.

3

Section 6.6 Recitals. The recitals and statements herein contained are made by the Company and New Albertson’s and not by the Agents, and the Agents assume no responsibility for the correctness thereof. The Agents make no representations as to the validity or sufficiency of this Supplemental Agreement.

Section 6.7 Holders of Certificates Bound. Every Holder of Certificates heretofore or hereafter authenticated, executed on behalf of the Holders and delivered under the Purchase Contract Agreement shall be bound hereby.

Section 6.8 Governing Law. This Supplemental Agreement and the rights and obligations of the parties hereunder shall be governed by and construed in accordance with the laws of the State of New York.

Section 6.9 Separability. If any one or more of the provisions contained in this Supplemental Agreement shall for any reason be held to be invalid, illegal or unenforceable in any respect, such invalidity, illegality or unenforceability shall not affect any other provisions of this Supplemental Agreement, but this Supplemental Agreement shall be construed as if such invalid or illegal or unenforceable provision had never been contained herein.

Section 6.10 Counterparts. This Supplemental Agreement may be executed in any number of counterparts, all of which taken together shall constitute one and the same instrument.

[SIGNATURE PAGES FOLLOW]

4

IN WITNESS WHEREOF, this First Supplement to the Pledge Agreement is executed as of the date first set forth above.

5