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 CSX Residual is a party which relate to any of said Senior Preferred Units or CSX-R Contract Rights.

(ii) CSX Domestic is the sole legal and beneficial owner of 6,000 Senior Preferred Units of the Company and 100 Common Units of the Company, which together constitute its entire Membership Interest in the Company, and has good, valid and merchantable title to such Senior Preferred Units and such Common Units, free and clear of all Liens. CSX Domestic has full authority to transfer complete and unencumbered title to such Senior Preferred Units and Common Units to HLPR pursuant to the terms of this Agreement. CSX Domestic 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-D Contract Rights”) to any third party and holds the CSX-D 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 CSX Domestic is a party which relate to any of said Senior Preferred Units or Common Units or any of the CSX-R Contract Rights.

(b) Authority. Sellers have all requisite corporate power and authority to execute and deliver this Agreement and perform their respective obligations hereunder. The execution of this Agreement by Sellers and the delivery and performance by Sellers of this Agreement have been duly authorized. Any and all corporate acts and other proceedings required for the due and valid authorization, execution, delivery and performance by Sellers of this Agreement and the consummation by Sellers of the transfer of the Membership Interests (including, but not limited to, the Units recited herein as owned by Sellers, the CSX-R Contract Rights and the CSX-D Contract Rights) to Buyers have been validly and appropriately taken.

4

(c) Enforceability. This Agreement is a legal, valid and binding obligation of Sellers, enforceable against Sellers 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.

(d) No Conflicts. The execution and delivery of this Agreement by Sellers, and the performance by Sellers 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 encumbrances upon any of the properties or assets of either Seller under, (i) the bylaws or certificates of incorporation of Sellers, (ii) any contract or agreement to which either Seller is a party or by which any of the properties or assets of either Seller is bound, or (iii) any permit, law, rule, regulation, judgement, order or decree applicable to either Seller or to which any of the properties or assets of either Seller is subject.

5. Release. Each of CSX, CSX Alaska and the Sellers (each, a “Releasing Party”), on behalf of itself and the past, present and future subsidiaries, successors and assigns of itself (collectively, the “Related Persons”), hereby forever irrevocably releases and discharges the Company, the Buyers and their respective Related Persons (individually, a “Released Person” and, collectively, “Released Persons”), from any and all claims, demands, proceedings, causes of action, court orders, obligations, contracts, agreements (express or implied), debts and liabilities whatsoever, whether known or unknown, suspected or unsuspected, both at law and in equity, which such Releasing Party or any of its Related Persons now has, has ever had or may hereafter have against the Released Persons arising solely out of the rights of the Releasing Party or any of its Related Persons under Article 4 or Article 8 of the Horizon LLC Agreement or under this Agreement with respect to the redemption or repurchase of, or distributions with respect to, the Senior Preferred Units and the Common Units which are the subject of this Agreement. Notwithstanding the foregoing, this paragraph 5 shall not be deemed to affect the claims of the Releasing Parties in respect of their rights, in consideration of their covenants and agreements in this Agreement, (i) to receive the cash consideration from Buyers expressly specified in paragraph 2 of this Agreement, and (ii) arising under paragraph 3 of this Agreement.

6. Acknowledgements. Each of CSX, CSX Residual, and CSX Alaska hereby acknowledges and confirms that it has been notified by the Company and HLH of the transactions (the “Merger”) contemplated by the Amended and Restated Agreement and Plan of Merger, dated as of July 7, 2004, by and among H-Lines Holding Corp., H-Lines Subcorp., Horizon Lines Holding Corp. (“HLHC”), and TC Group, L.L.C. in accordance with the relevant terms of the Amended and Restated Guarantee and Indemnity Agreement, dated February 27, 2003, by and among HLH, the Company, CSX, CSX Alaska and CSX Residual (the “GIA”) and that they have received the joinder agreements, officers’ certificate(s) and legal opinions specified to be delivered pursuant to Sections 11.01(b), 11.02(b)(5) and 11.02(b)(6) of the GIA.

5

7. Amendment; Waivers. Any provision of this Agreement may be amended or modified at any time by an agreement in writing among the parties hereto approved by their respective authorized signatories and executed in the same manner as this Agreement.

8. Execution in Counterparts. This Agreement may be executed in multiple counterparts, each of which shall be deemed to constitute an original. Each such counterpart shall become effective when one counterpart has been signed by each party hereto.

9. Governing Law. This Agreement shall be governed by, and interpreted in accordance with, the laws of the State of Delaware applicable to agreements made and to be entirely performed within such State, except as federal law may be applicable.

10. Expenses. Each party hereto will bear all expenses incurred by it in connection with this Agreement and the transactions contemplated hereby, without prejudice to Section 11.02(b) of the GIA.

11. No Assignment. No party hereto may assign any of its rights or obligations under this Agreement to any other person without the prior written consent of each other party hereto, excluding any transfer or assignment by operation of law.

12. Headings. The headings in this Agreement are inserted for convenience of reference only and are not intended to be a part of or to affect the meaning or interpretation of this Agreement.

13. Entire Agreement. This Agreement supersedes any and all oral or written agreements and understandings heretofore made relating to the subject matter hereof and contains the entire agreement of the parties relating to the subject matter hereof. The terms and conditions of this Agreement shall inure to the benefit of and be binding upon the parties hereto. Nothing in this Agreement is intended to or shall be construed to confer upon or to give any person other than the parties hereto any rights, remedies, obligation or liabilities under or by reason of this Agreement except as expressly provided herein.

14. Further Assurances. Each party hereto agrees to take all such further action as may be necessary or desirable to effectuate the purposes of this Agreement, including the execution, delivery and filing, as the case may be, of certificates, acknowledgments, membership transfer powers and lien releases.

15. Interpretation. No provision of this Agreement shall be interpreted for or against any party because that party or its legal representative drafted the provision.

6

IN WITNESS WHEREOF, the parties hereto have caused this instrument to be executed in counterparts as of the date hereof.

7

IN WITNESS WHEREOF, the parties hereto have caused this instrument to be executed in counterparts as of the date hereof.

8