MEMBERSHIP INTEREST PURCHASE AND SALE AGREEMENT

Exhibit 10.1

MEMBERSHIP INTEREST PURCHASE AND SALE AGREEMENT

THIS MEMBERSHIP INTEREST PURCHASE AND SALE AGREEMENT (this “Agreement”), dated and effective as of July 7, 2004, is entered into by and among HLH, LLC, a Delaware limited liability company formerly known as Delian Holdings, L.L.C. (“HLH”), Horizon Lines of Puerto Rico, Inc., a Delaware corporation (“HLPR,” and, collectively with HLH, “Buyers”), CSX Domestic Shipping Corporation, a Delaware corporation (“CSX Domestic”), CSX Residual Company, a Delaware corporation (“CSX Residual,” and, collectively with CSX Domestic, “Sellers”), CSX Corporation, a Virginia corporation (“CSX”), and CSX Alaska Vessel Company, LLC, a Delaware limited liability company (“CSX Alaska”). All capitalized terms used but not defined herein shall have the meanings given to them in the Amended and Restated Limited Liability Company Agreement of Horizon Lines, LLC (the “Company”), dated as of February 27, 2003, as heretofore amended, supplemented or otherwise modified (the “Horizon LLC Agreement”).

WHEREAS, CSX Residual is the record and beneficial owner of a Membership Interest in the Company consisting of 54,000 Senior Preferred Units and desires to sell all such Senior Preferred Units to HLH in exchange for cash and HLH desires to purchase all such Senior Preferred Units from CSX Residual.

WHEREAS, CSX Domestic is the record and beneficial owner of a Membership Interest in the Company consisting of 6,000 Senior Preferred Units and 100 Common Units and desires to sell all such Senior Preferred Units and Common Units to HLPR in exchange for cash, and HLPR desires to purchase all such Senior Preferred Units and Common Units from CSX Domestic.

NOW, THEREFORE, in consideration of the mutual covenants and agreements made herein, and other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties agree as follows:

1. Purchase and Sale of Membership Interests, etc. Upon the execution and delivery of this Agreement, the parties hereby agree as follows:

(a) CSX Residual hereby assigns, sells, transfers and delivers to HLH (for its own account), and HLH hereby purchases, acquires and accepts from CSX Residual, (i) all of CSX Residual’s right, title and interest in and to 54,000 Senior Preferred Units of the Company, free and clear of all liens, pledges, encumbrances, charges, and claims thereon, (ii) all of CSX Residual’s right and interest in and to the Capital Account for such Senior Preferred Units under the Horizon LLC Agreement and (iii) all of CSX Residual’s right and interest under the Horizon LLC Agreement in respect of its status as a Senior Preferred Member and holder of Senior Preferred Units thereunder;

(b) CSX Domestic hereby assigns, sells, transfers and delivers to HLPR (for its own account), and HLPR hereby purchases, acquires and accepts from CSX

Domestic, (i) all of CSX Domestic’s right, title and interest in and to 6,000 Senior Preferred Units of the Company, free and clear of all liens, pledges, encumbrances, charges, and claims thereon, (ii) all of CSX Domestic’s right and interest in and to the Capital Account for such Senior Preferred Units under the Horizon LLC Agreement and (iii) all of CSX Domestic’s right and interest under the Horizon LLC Agreement in respect of its status as a Senior Preferred Member and holder of Senior Preferred Units thereunder;

(c) CSX Domestic hereby assigns, sells, transfers and delivers to HLPR (for its own account), and HLPR hereby purchases, acquires and accepts from CSX Domestic, (i) all of CSX Domestic’s right, title and interest in and to 100 Common Units of the Company, free and clear of all liens, pledges, encumbrances, charges, and claims thereon, (ii) all of CSX Domestic’s right and interest in and to the Capital Account for such Common Units under the Horizon LLC Agreement and (iii) all of CSX’s right and interest under the Horizon LLC Agreement in respect of its status as a Common Member and holder of such Common Units thereunder; and

(d) Sellers hereby cease to be parties to the Horizon LLC Agreement and hereby cease to have any rights thereunder;

provided, however, that notwithstanding anything to the contrary in this paragraph 1, except as contemplated in paragraph 5 of this Agreement, Sellers are not releasing or transferring to Buyers any rights or claims, absolute or contingent, under the Horizon LLC Agreement in respect of (X) indemnities contained therein, including, without limitation, Section 6.6 thereof, and (Y) breaches of covenants or other obligations thereunder arising on or prior to the effective date of this Agreement, and Sellers shall retain all such rights and claims.

2. Consideration.

(a) Concurrently with the execution and delivery of this Agreement, HLH is paying to CSX Residual, and CSX Residual accepts, $52,886,279.70 in cash by wire transfer of immediately available funds from an account in the name of H-Lines Holding Corp. to the account designated on Exhibit A hereto in full payment in exchange for the transfer of the Senior Preferred Units described above in paragraph 1(a).

(b) Concurrently with the execution and delivery of this Agreement, HLPR is paying to CSX Domestic, and CSX Domestic accepts, $5,876,253.30 in cash by wire transfer of immediately available funds from an account in the name of H-Lines Holding Corp. to the account designated on Exhibit A hereto in full payment in exchange for the transfer of the Senior Preferred Units described above in paragraph l(b).

(c) Concurrently with the execution and delivery of this Agreement, HLPR is paying to CSX Domestic, and CSX Domestic accepts, $100,000 in cash by wire

2

transfer of immediately available funds from an account in the name of H-Lines Holding Corp. to the account designated on Exhibit A hereto in full payment in exchange for the transfer of the Common Units described above in paragraph l(c).

3. Representations and Warranties of Buyers. Buyers hereby represent and warrant to Sellers as follows:

(a) Authority. Buyers have all requisite corporate or limited liability company power and authority to execute and deliver this Agreement and perform their respective obligations hereunder. The execution of this Agreement by Buyers and the delivery and performance by Buyers of this Agreement have been duly and validly authorized. Any and all corporate acts and other proceedings required for the due and valid authorization, execution, delivery and performance by Buyers of this Agreement and the consummation by Buyers of the transfer of the Membership Interests to Buyers have been validly and appropriately taken.

(b) Enforceability. This Agreement is a legal, valid and binding obligation of Buyers, enforceable against Buyers in accordance with its terms, except that enforcement may be limited by bankruptcy, reorganization, insolvency and other similar laws and court decisions relating to or affecting the enforcement of creditors’ rights generally and by general equitable principles.

(c) No Conflicts. The execution and delivery of this Agreement by Buyers, and the performance by Buyers of their respective obligations under this Agreement, will not result in any conflict with, or result in a violation or breach of any of the provisions of, or constitute (with or without due notice, lapse of time or both) a default under, or give rise to a right of termination, cancellation or acceleration of any obligation under, or result in the creation of any lien or other encumbrance upon any of the properties or assets of either Buyer under, (i) the bylaws or certificate of incorporation of HLPR or the limited liability company agreement of HLH, (ii) any contract or agreement to which either Buyer is a party or by which any of the properties or assets of either Buyer is bound, or (iii) any permit, law, rule, regulation, judgment, order or decree applicable to either Buyer or to which any of the properties or assets of either Buyer is subject.

(d) Puerto Rico EBITDA. The Actual Puerto Rico EBITDA for the calendar year ending 2003 does not exceed $31,700,000. The Actual Puerto Rico EBITDA for the period beginning on January 1, 2004 and ending on June 30, 2004 does not exceed $17,150,000.

(e) Citizenship. Each Buyer is a Citizen of the United States (as defined in the GIA).

3

4. Representations and Warranties of Sellers. Sellers hereby represent and warrant to Buyers as follow:

(a) Ownership of Membership Units.

(i) CSX Residual is the sole legal and beneficial owner of 54,000 Senior Preferred Units of the Company, which constitute its entire Membership Interest in the Company, and has good, valid and merchantable title to such Senior Preferred Units, free and clear of all mortgages, liens, pledges, restrictions, security interests, charges, preferential purchase rights and other encumbrances of any nature (“Liens”). CSX Residual has full authority to transfer complete and unencumbered title to such Senior Preferred Units to HLH pursuant to the terms of this Agreement. CSX Residual has not assigned any of its rights or interests under the Horizon LLC Agreement in respect of its status as a Member or holder of Units thereunder (“CSX-R Contract Rights”) to any third party and holds the CSX-R Contract Rights free and clear of all Liens. Except for this Agreement and the Horizon LLC Agreement, there are no contracts or agreements to which C