Exhibit 10.1

AMENDED AND RESTATED RESTRUCTURING SUPPORT AGREEMENT

This AMENDED AND RESTATED RESTRUCTURING SUPPORT AGREEMENT (as it may be amended, supplemented or otherwise modified as provided herein, this “RSA”), initially dated as of March 26, 2012 and amended and restated as of April 9, 2012, is by and between Horizon Lines, Inc. (the “Parent”), and all of its subsidiaries (collectively with the Parent, the “Company”) and the holder set forth on the signature page hereto (the “Participating Holder”) of the (i) 11.00% first lien secured notes due 2016 (the “First Lien Secured Notes”) issued under the Indenture, dated as of October 5, 2011 (as amended, supplemented, or modified from time to time, the “First Lien Notes Indenture”), by and between Horizon Lines, LLC, as issuer, and U.S. Bank National Association, as Trustee, in the initial aggregate principal amount of $225,000,000.00, (ii) 13-15% second lien secured notes due 2016 (the “Second Lien Secured Notes”) issued under the Indenture, dated as of October 5, 2011 (as amended, supplemented, or modified from time to time, the “Second Lien Notes Indenture”), by and between Horizon Lines, LLC, as issuer, and U.S. Bank National Association, as Trustee, in the aggregate principal amount of $100,000,000.00, or (iii) 6.00% Series A Convertible Senior Secured Notes due 2017 and 6.00% Series B Mandatorily Convertible Senior Secured Notes (the “Convertible Secured Notes”, together with the First Lien Secured Notes and the Second Lien Secured Notes, the “Notes”) issued under the Indenture, dated as of October 5, 2011 (as amended, supplemented, or modified from time to time, the “Convertible Notes Indenture”), by and between the Parent, as issuer, and U.S. Bank National Association, as Trustee, in the aggregate principal amount of $180,000,000.00 in the case of the Series A Convertible Notes and $100,000,000 in the case of the Series B Convertible Notes. The principal amount of Notes held by the Participating Holders (as defined below) is set forth on a confidential schedule maintained by Paul, Weiss, Rifkind, Wharton & Garrison LLP (“Paul, Weiss”). The Participating Holder, the Company, and each other person that becomes a party hereto in accordance with the terms hereof shall be referred to herein individually as a “Party” and, collectively, as the “Parties.” References herein to a percentage of Participating Holders refer to the principal amount of the Notes held by such Participating Holders relative to the aggregate principal amount of the applicable class of Notes outstanding.

RECITALS

WHEREAS, prior to the date hereof, representatives of the Company and the Participating Holder have discussed (i) consummating a solicitation of consents under the First Lien Notes Indenture, the Second Lien Notes Indenture and the Convertible Notes Indenture (the “Consent Solicitation”), upon the terms and subject to the conditions set forth in the consent solicitation statement for the First Lien Notes Indenture (in substantially the form delivered to The Depositary Trust Company on or about March 30, 2012, the “First Lien Consent”), for the Second Lien Notes Indenture (in substantially the form delivered to The Depositary Trust Company on or about March 30, 2012, the “Second Lien Consent”) and for the Convertible Notes Indenture (in substantially the form delivered to The Depositary Trust Company on or about March 30, 2012, the “Convertible Notes Consent”; together with the First Lien Consent and the Second Lien Consent, in each case as may be amended, supplemented or otherwise modified from time to time, the “Consent Solicitation Statements”) and (ii) certain potential transactions to restructure certain vessel charters (the “Charters”) regarding the D8 Vessels (such restructuring, the “D8 Restructuring”) involving, among other parties, Ship Finance International Limited (together with its subsidiaries, “SFL”);

WHEREAS, subject to the terms and conditions set forth herein, the following sets forth the agreement among the Parties concerning the Consent Solicitation and the D8 Restructuring.

AGREEMENT

NOW, THEREFORE, in consideration of the covenants and agreements contained herein, and for other valuable consideration, the receipt and sufficiency of which is hereby acknowledged, each Party, intending to be legally bound hereby, agrees as follows:

1. Definitions. The following terms shall have the following definitions:

“Bankruptcy Code” means Title 11 of the United States Code, 11 U.S.C. §§ 101–1532.

“Business Day” means any day other than Saturday, Sunday and any day that is a legal holiday or a day on which banking institutions in New York, New York are authorized by law or other governmental action to close.

“Charters” those certain agreements for five 2,824 TEU container vessels that are individually chartered to Horizon Lines, LLC by five special-purpose subsidiaries of SFL, which vessels are financed by Credit Agreement dated April 7, 2006, providing for a $210,000,000 senior secured term loan.

“Confidentiality Agreement” means the separate confidentiality agreements between each Participating Holder and the Parent.

“Consent Solicitation Documentation” means the Letter of Consent (as defined in the Consent Solicitation Statements) and any other required documents, including the Letter of Instruction (as defined in the Consent Solicitation Statements), to be delivered by the Participating Holder in connection with the Consent Solicitation to the Information and Tabulation Agent (as defined in the Consent Solicitation Statements) or another appropriate party.

“Conversion” means conversion of substantially all of the Convertible Secured Notes into 90% of the Parent’s common stock or warrants for non-U.S. citizens (subject to dilution for a limited amount of equity retention for existing equity holders on terms to be agreed and a management incentive plan), with the remaining 10% of Parent’s common stock to be available to satisfy obligations of the Company, including in connection with the D8 Restructuring.

“Majority RSA Noteholders” means RSA Noteholders holding more than 50% of the aggregate principal amount of Notes outstanding.

“Noteholders” means each entity that is a beneficial holder of the First Lien Secured Notes, the Second Lien Secured Notes and/or the Convertible Secured Notes, as applicable.

“Person” means an individual, a partnership, a joint venture, a limited liability company, a corporation, a trust, an unincorporated organization, a group or any legal entity or association.

“RSA Noteholders” means Noteholders party to a RSA and a similar RSA.

“Securities Act” means Securities Act of 1933, as amended.

“Similar RSA” means a restructuring support agreement with substantially identical terms to this RSA entered into by the Company and a Noteholder.

2. Consent Solicitation. The Participating Holder represents to the Company that it has taken all necessary action to instruct its custodians to execute the Consent Solicitation Documentation and grant the Consent Solicitation. The Participating Holder agrees that it will not revoke, withdraw or amend any Consent Solicitation Documentation or instructions. The Company shall not consummate the Consent Solicitation until such time as: (i) the Charters shall have been terminated and the D8 Restructuring shall have been consummated, and all of the Company’s obligations under the guarantee and all other transaction documents entered into in connection with the Charters have been released and (ii) Noteholders representing at least 90% of the aggregate principal amount of Second Lien Notes and Noteholders representing at least 90% of the aggregate principal amount of Convertible Secured Notes become parties to Similar RSAs. The Company represents to the Participating Holder that it has Similar RSAs (together with this RSA) from Noteholders representing at least 99% of the aggregate principal amount of Second Lien Notes.

3. Conversion. The Participating Holder represents to the Company that it has taken all necessary action to effect the Conversion, including delivery of irrevocable conversion notices consistent with the terms of the Convertible Notes Indenture and agrees that immediately upon consummation of the D8 Restructuring and the Consent Solicitation, the Company may take all necessary action to consummate the Conversion. The Company represents to the Participating Holder that it has received notices of Conversion for at least 99% of the aggregate principal amount of Convertible Secured Notes.

4. Transfer of Notes. The Participating Holder agrees that as long as a Termination Event has not occurred or has occurred but has been duly waived in accordance with the terms hereof, it shall not (and shall cause each of its affiliates, subsidiaries, representatives, agents, and employees not to) sell, transfer or assign, or grant, issue or sell any option, right to acquire, voting participation or other interest in (each, a “Transfer”) any Notes, as applicable, unless the following two criteria are met: (i) the transferor Participating Holder notifies Paul, Weiss of the Transfer and the principal amount of Notes to be transferred thereby; and (ii) the transferee party first agrees in writing to be subject to the terms and conditions of this RSA or a Similar RSA as a

“Participating Holder,” and executes a counterpart signature page to this RSA or a Similar RSA. Any Transfer that does not comply with the foregoing shall be deemed void ab initio. This RSA shall in no way be construed to preclude the Participating Holder from acquiring additional Notes, provided that any such additional Notes shall automatically be deemed to be subject to the terms of this RSA. In addition, for so long as this RSA has not been terminated in accordance with its terms, a Participating Holder may offer, sell or otherwise transfer any or all of its Notes to any of its affiliates, who shall be automatically deemed bound by this RSA as a Participating Holder; provided, however, Paul, Weiss shall be provided by such Participating Holder prompt notice of any such offer, sale, or transfer. The confidential schedule of the principal amount of Notes held by the Participating Holders and any transfer notices provided to Paul, Weiss in connection with the foregoing will be made available on a name redacted, confidential basis to counsel for the Company and shall not be disclosed by such counsel to the Company or any third party.

5. Termination.

This RSA, together with Similar RSAs, may be terminated upon the occurrence of any of the following events together with written notice thereof by the Parties asserting termination to the other Parties (each a “Termination Event” and the date on which this RSA is terminated in accordance herewith, the “Termination Date”):

5.1 by any RSA Noteholder as to itself:

5.2 By the Company:

5.3 by the mutual consent of the Company and Majority RSA Noteholders.

5.4 automatically, in the event cases under the Bankruptcy Code are commenced by or against the Company in any jurisdiction, and solely in the event of an involuntary filing against the Company, such involuntary case is not dismissed within fifteen (15) days of filing.

5.5 automatically, on April 30, 2012.

6. Good Faith Cooperation; Further Assurances. As long as a Termination Event has not occurred, the Company hereby covenants and agrees to cooperate in good faith with all information requests reasonably made by advisors to the Participating Holder that are necessary or advisable for the Participating Noteholders to evaluate the Transaction, and further covenants and agrees to deliver such information requested on a timely basis.

7. Effectiveness. This RSA will be effective and binding upon the Company and the undersigned Participating Holder as of the date on which: (i) the Company shall have executed and delivered counterpart signature pages of this RSA and the Similar RSAs described in clause (iii) below to counsel to the Participating Holder, (ii) the Participating Holder shall have executed and delivered counterpart signature pages of this RSA to counsel to the Company, and (iii) the Participating Holders representing the percentage of outstanding Notes agreed to by counsel for the Company and counsel for the Participating Holders shall have executed and delivered (through its respective counsel) counterpart signature pages of this RSA and the Similar RSAs to counsel to the Company.

8. Entire Agreement. This RSA constitutes the entire agreement of the Company and the Participating Holder with respect to the subject matter of this RSA, and supersedes all other prior negotiations, agreements and understandings, whether written or oral, among the Parties with respect to the subject matter of this RSA, other than the

Confidentiality Agreement which remains unaltered; provided, however, that, notwithstanding anything to the contrary in the Confidentiality Agreement, the Termination Date (as defined in the Confidentiality Agreement) shall be amended to April 16, 2012.

9. Reservation of Rights. Except as expressly provided in this RSA, nothing herein is intended to, or does, in any manner waive, limit, impair or restrict the ability of each Party to protect and preserve its rights, remedies, and interests, including, without limitation, its claims against other Parties or their respective affiliates, and all rights are reserved if the Consent Solicitation and the D8 Restructuring is not consummated. Nothing herein shall be deemed an admission of any kind. Nothing contained herein effects a modification of the Company’s, the Participating Holder’s or the trustee’s rights under the First Lien Secured Notes, the Second Lien Secured Notes or the Convertible Secureds Notes, the First Lien Notes Indenture, the Second Lien Notes Indenture or the Convertible Notes Indenture or other related documents and agreements.

10. Waiver. This RSA is part of a proposed settlement of matters that could otherwise be the subject of litigation among the Parties hereto. If the transactions contemplated herein are not consummated, or following the occurrence of the Termination Date, if applicable, nothing shall be construed herein as a waiver by any Party of any or all of such Party’s rights and the Parties expressly reserve any and all of their respective rights. Pursuant to Federal Rule of Evidence 408 and any other applicable rules of evidence, this RSA and all negotiations relating hereto shall not be admissible into evidence in any proceeding other than a proceeding to enforce its terms.

11. Payment of Fees and Expenses. The Company agrees to pay all reasonable, hourly fees and expenses of Paul, Weiss and any other specialty shipping advisors and other specialists engaged by the Noteholders, as reasonably required and engaged upon advance written notice to the Company, in connection with conducting ongoing due diligence and negotiating, documenting and consummating the Consent Solicitation and the D8 Restructuring.

12. Counterparts. This RSA may be executed in one or more counterparts, each of which, when so executed, shall constitute the same instrument and the counterparts may be delivered by facsimile transmission or by electronic mail in portable document format (.pdf).

13. Amendments. Except as otherwise provided herein, this RSA may not be modified, amended or supplemented, or any provisions herein or therein waived without the prior written consent of RSA Noteholders holding at least two-thirds of the aggregate principal amount of Notes outstanding (and may be modified, amended or supplemented with such consent).

14. Headings. The headings of the sections, paragraphs and subsections of this RSA are inserted for convenience only and shall not affect the interpretation hereof.

15. Relationship Among Parties. It is understood and agreed that any Participating Holder may trade in the Notes or other debt or equity securities of the Company without the consent of the Company or any Participating Holder, subject to applicable securities laws and Section 4 hereof. No Party shall have any responsibility for any such trading by any other entity by virtue of this RSA. No prior history, pattern or practice of sharing confidences among or between Parties shall in any way affect or negate this understanding and agreement. For the avoidance of doubt, (i) the execution of this RSA by any Participating Holder shall not create, or be deemed to create, any fiduciary or other duties (actual or implied) to any other Participating Holder other than as expressly set forth in this RSA and (ii) no Exchanging Holder shall be responsible for, or have any obligation with respect to, any duties or obligations of any other Participating Holder under a Similar RSA.

16. Specific Performance. It is understood and agreed by the Parties that money damages would be an insufficient remedy for any breach of this RSA by any Party and each non-breaching Party shall be entitled to seek specific performance and injunctive or other equitable relief as a remedy of any such breach, including, without limitation, an order of a court of competent jurisdiction requiring any Party to comply promptly with any of its obligations hereunder.

17. Survival. Notwithstanding (i) any Transfer of the Notes in accordance with Section 4 of this RSA or (ii) the termination of this RSA in accordance with its terms, the agreements and obligations of the Parties in Section 8, 9, 10, 11 15, and 21 and this Section 17 shall survive such Transfer and/or termination and shall continue in full force and effect for the benefit of the Parties in accordance with the terms hereof.

18. Governing Law. This RSA shall be governed by, and construed in accordance with, the laws of the State of New York, without regard to such state’s choice of law provisions which would require the application of the law of any other jurisdiction.

19. Notices. All notices, requests and other communications hereunder must be in writing and will be deemed to have been duly given only if delivered personally or by electronic mail transmission with first class mail confirmation to the Parties at the following addresses or email addresses:

If to the Company:

Horizon Lines, LLC

Michael T. Avara

4064 Colony Road, Suite 200

Charlotte, North Carolina 28211

with a copy to (which shall not constitute notice):

Edward O. Sassower

Joshua A. Sussberg

Kirkland & Ellis LLP

601 Lexington Avenue

New York, New York 10022

E-mail: jsussberg@kirkland.com

If to the Participating Holder:

To the addresses and email addresses set forth on the signature pages hereto.

with a copy to (which shall not constitute notice):

Andrew Rosenberg

Paul, Weiss, Rifkind, Wharton & Garrison LLP

1285 Avenue of the Americas

New York, New York 10019

E-mail: arosenberg@paulweiss.com

20. No Third-Party Beneficiaries. The terms and provisions of this RSA are intended solely for the benefit of the Parties and their respective successors and permitted assigns, and it is not the intention of the Parties to confer third-party beneficiary rights upon any other Person. No Participating Holder shall have any right to enforce the terms of any Similar RSA against any other Participating Holder.

21. Public Disclosure. The Company will submit to the Participating Holder all press releases and public filings relating to this RSA or the transactions contemplated hereby and thereby and any amendments thereof. The Company shall not (a) use the name of the Participating Holder or its manager, advisor, or affiliates in any press release without such Party’s prior written consent or (b) disclose holdings of the Participating Holder to any Person; provided, however, that the Company shall be permitted to disclose at any time the aggregate principal amount of and aggregate percentage of Notes held by the Participating Holders.

IN WITNESS WHEREOF, the Parties hereto have caused their duly authorized officers to execute and deliver this RSA as of the date first above written.

Signature Page to Restructuring Support Agreement

Signature Page to Restructuring Support Agreement

Signature Page to Restructuring Support Agreement

Signature Page to Restructuring Support Agreement