Exhibit 10.1

EXECUTION VERSION

RESTRUCTURING SUPPORT AGREEMENT

This RESTRUCTURING SUPPORT AGREEMENT (as it may be amended, supplemented or
otherwise modified as provided herein, this “RSA”), dated as of March 26, 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 attached hereto as
Exhibit A, the “First Lien Consent”), for the Second Lien Notes Indenture (in
substantially the form attached hereto as Exhibit B, the “Second Lien Consent”)
and for the Convertible Notes Indenture (in substantially the form attached
hereto as Exhibit C, 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.

 

2

--------------------------------------------------------------------------------

“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. By no later than 5:00 p.m. New York City time, on
March 29, 2012, the Participating Holder shall submit to the Information and
Tabulation Agent (as defined in the Consent Solicitation Statements), with a
copy thereof provided to Paul, Weiss, fully executed Consent Solicitation
Documentation for all Notes held by the Participating Holder. So long as a
Termination Event has not occurred, the Participating Holder agrees that it will
not revoke, withdraw or amend its Consent Solicitation Documentation, except to
supplement the Consent Solicitation Documentation to include any Notes acquired
after the date hereof. The Company shall not consummate the Consent Solicitation
until such time as: (a) the Charters shall have been terminated 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
(b) Noteholders representing 90% of the aggregate principal amount of Second
Lien Notes and Noteholders representing 90% of the aggregate principal amount of
Convertible Secured Notes become parties to Similar RSAs and have delivered
fully executed Consent Solicitation Documentation to the Information and
Tabulation Agent.

3. D8 Restructuring. So long as a Termination Event has not occurred, and
subject to definitive documentation and satisfactory completion of due
diligence, the Parties hereby agree to the Conversion and the Parties agree to
work in good faith to negotiate the terms of the D8 Restructuring and complete
definitive documentation to implement the D8 Restructuring on or before April 5,
2012.

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

 

3

--------------------------------------------------------------------------------

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:

 

  (a) if the Company shall have breached any of its material obligations under
the RSA or Similar RSA as set forth herein or therein;

 

  (b) if any Event of Default has occurred and is continuing under any of the
First Lien Notes Indenture, the Second Lien Notes Indenture or the Convertible
Notes Indenture;

 

  (c) if any event of default has occurred and is continuing under the Charter
(or the term loan financing relating thereto);

 

  (d) if any material amendment, waiver, forbearance or modification to the
Company’s existing asset-based credit facility permitting the Consent
Solicitation or the D8 Restructuring shall not be in form and substance
reasonably satisfactory to Majority RSA Noteholders;

 

  (e) if the Company fails to consummate the Consent Solicitation by April 5,
2012;

 

  (f) if by April 5, 2012, the Charters have not been restructured on terms
satisfactory to the Participating Noteholder (in its sole discretion), pursuant
to a termination agreement or otherwise, and all of the Company’s obligations
under the guarantee and all other transaction documents entered into in
connection with the Charters have not been released;

 

4

--------------------------------------------------------------------------------

  (g) if by April 5, 2012, the Company and the RSA Noteholders have not
(i) reached agreement on definitive documentation, in form and substance
reasonably satisfactory to the Participating Holder, to implement the D8
Restructuring and (ii) executed an amendment to the RSA and all Similar RSAs to
reflect an agreement to support the D8 Restructuring;

 

  (h) if by April 5, 2012, the Participating Holder is not satisfied, in its
sole discretion, with (a) the scope or nature of the Company’s financial and
other reporting obligations to the Securities and Exchange Commission that will
continue to be in effect following consummation of any D8 Restructuring or
(b) any agreement by the Company to cease, as soon as practicable following
consummation of any D8 Restructuring, to be a SEC reporting company; or

 

  (i) if any court of competent jurisdiction or other competent governmental or
regulatory authority shall have issued an order making illegal or otherwise
restricting, preventing, or prohibiting the Consent Solicitation or the D8
Restructuring in a material way that cannot be reasonably remedied by the
Parties.

 

  5.2 by the Company:

 

  (a) if any court of competent jurisdiction or other competent governmental or
regulatory authority shall have issued an order making illegal or otherwise
restricting, preventing, or prohibiting the Consent Solicitation and the D8
Restructuring in a material way that cannot be reasonably remedied by the
Parties; or

 

  (b) if the directors of the Parent determine in good faith that continued
performance under this RSA would be inconsistent with the exercise of fiduciary
duties under applicable law.

 

  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.

 

5

--------------------------------------------------------------------------------

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 13, 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.

 

6

--------------------------------------------------------------------------------

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.

 

7

--------------------------------------------------------------------------------

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.

 

8

--------------------------------------------------------------------------------

EXECUTION VERSION

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.

 

HORIZON LINES, INC. By:  

 

  Name:   Title: HORIZON LINES HOLDING CORP. By:  

 

  Name:   Title: HORIZON LINES, LLC By:  

 

  Name:   Title: HORIZON LINES OF PUERTO RICO, INC. By:  

 

  Name:   Title:

HAWAII STEVEDORES, INC.

By:  

 

  Name:   Title:

Signature Page to Restructuring Support Agreement

--------------------------------------------------------------------------------

 

HORIZON LOGISTICS, LLC

By:  

 

  Name:   Title:

H-L DISTRIBUTION SERVICE, LLC

By:  

 

  Name:   Title:

HORIZON LINES OF ALASKA, LLC

By:  

 

  Name:   Title:

HORIZON LINES OF GUAM, LLC

By:  

 

  Name:   Title:

HORIZON LINES VESSELS, LLC

By:  

 

  Name:   Title:

Signature Page to Restructuring Support Agreement

--------------------------------------------------------------------------------

SEA-LOGIX, LLC By:  

 

  Name:   Title:

AERO LOGISTICS, LLC

By:  

 

  Name:   Title:

HORIZON SERVICES GROUP, LLC

By:  

 

  Name:   Title:

Signature Page to Restructuring Support Agreement

--------------------------------------------------------------------------------

PARTICIPATING HOLDER:

[INSERT NAME OF PARTICIPATING HOLDER]

By:

 

 

  Name:  

 

  Title:  

 

Signature Page to Restructuring Support Agreement

--------------------------------------------------------------------------------

EXHIBIT A

Form of First Lien Consent

--------------------------------------------------------------------------------

EXHIBIT B

Form of Second Lien Consent

--------------------------------------------------------------------------------

EXHIBIT C

Form of Convertible Notes Consent