SECOND SUPPLEMENTAL INDENTURE (TO SECOND LIEN INDENTURE)

Exhibit 10.1

SECOND SUPPLEMENTAL INDENTURE

(TO SECOND LIEN INDENTURE)

THIS SECOND SUPPLEMENTAL INDENTURE (this “Supplemental Indenture”) is dated as of July 17, 2012, and has been entered into by and between Horizon Lines, LLC, a Delaware limited liability company, having its principal office at 4046 Colony Road, Suite 200, Charlotte, North Carolina 28211 (the “Company”), the guarantors listed on the signature pages hereto (the “Guarantors”) and U.S. Bank National Association, as trustee (the “Trustee”) and collateral agent.

RECITALS

WHEREAS, the Company, the Guarantors and the Trustee previously entered into that certain indenture dated as of October 5, 2011 as amended by that certain first supplemental indenture dated as of April 9, 2012 (as amended, the “Indenture”), providing for the issuance of the Company’s Second Lien Senior Secured Notes due 2016 (the “Notes”);

WHEREAS, Notes in the aggregate principal amount of $147,917,000 are currently outstanding under the Indenture;

WHEREAS, Section 11.02 of the Indenture provides that the Company may enter into an indenture or indentures supplemental to the Indenture for the purpose of adding any provisions to or changing in any manner or eliminating any of the provisions of the Indenture or of modifying in any manner the rights of the Holders of Notes under the Indenture, in certain cases, with written consent of the Holders of not less than a majority in aggregate principal amount of the outstanding Notes voting as a single class (including, without limitation, consents obtained in connection with a purchase of, or tender offer or exchange offer for, Notes), by the act of such Holders delivered to the Company and the Trustee, provided that such amendments apply only to consenting holders;

WHEREAS, Section 11.02 of the Indenture further provides that any amendment to, or waiver of, the provisions of the Indenture that has the effect of modifying or amending the last paragraph of Section 2.13 of this Indenture shall require the consent of Holders of at least 90% in aggregate principal amount of the Notes then outstanding under the Indenture;

WHEREAS, the Company conducted a consent solicitation and exchange offer (the “Offer”), pursuant to which Holders of $147,916,651 in aggregate principal amount, representing 99.9998% of the outstanding Notes, consented to the Proposed Amendments (as defined in the Consent Solicitation and Exchange Statement with respect to the Notes, dated May 30, 2012 (the “Statement”)) to certain terms and provisions in the Indenture;

WHEREAS, such consents have been delivered to the Information and Tabulation Agent, as identified in the Statement, and were not validly withdrawn;

WHEREAS, pursuant to the Statement, Notes held by Holders who gave their consent to the Proposed Amendments (as defined in the Statement), will trade under a new CUSIP number to reflect the Proposed Amendments (as defined in the Statement) (the “Exchange Notes”);

WHEREAS, the Company has been authorized by Board Resolution to enter into this Supplemental Indenture;

WHEREAS, the Company desires to amend certain provisions of the Indenture, as set forth in Article I of this Supplemental Indenture to effect the Proposed Amendments;

WHEREAS, all acts and requirements necessary to make this Supplemental Indenture the legal, valid and binding obligation of the Company and the Guarantors have been done; and

WHEREAS, the Company has received and delivered to the Trustee the requisite consents to effect the Proposed Amendments under the Indenture.

AGREEMENT

NOW, THEREFORE, in consideration of the premises and the covenants and agreements contained herein, and for other good and valuable consideration the receipt of which is hereby acknowledged, and for the equal and proportionate benefit of the Holders of the Notes, the Company and the Trustee hereby agree as follows:

ARTICLE I

AMENDMENTS TO INDENTURE

Section 1.01 Exchange Notes. The Exchange Notes issued to holders of Notes who gave their consent to the Proposed Amendments will be substantially in the form of Exhibit A hereto.

Section 1.02 Amendments to the Indenture. The Indenture is hereby amended as follows:

(a) The provisions of Section 2.13 of the Indenture following the first paragraph of Section 2.13 are hereby amended and restated in its entirety to read as follows:

In the event that an Additional Note is issued pursuant to this Section 2.13 and in reliance on Section 4.11(b)(xxiii) in an amount not to exceed $40.0 million in aggregate principal amount (such Additional Note, the “New Note”), the initial holder of the New Note shall have the right, only upon the occurrence of an Event of Default under Section 7.01(a)(vi) and only if such initial holder shall continue to hold the entire initial principal amount of the New Note, to purchase all, but not less than all, other outstanding Notes from the First Supplemental Consenting Holders thereof at a purchase price equal to the principal amount of such Notes, plus accrued and unpaid interest to, but not including, the date of purchase. Such purchase shall be consummated upon reasonable notice to the Trustee and the First Supplemental Consenting Holders of the Notes and upon such other terms as shall be reasonably acceptable to the Trustee, except that any such purchase notice to the Trustee and the First Supplemental Consenting Holders shall be given no later than 15 days before the date of such purchase. Provided that the initial holder of the New Note has caused the deposit of funds with the Trustee sufficient to consummate the purchase of the outstanding Notes on the purchase date, the Notes subject to the purchase right shall be deemed automatically transferred by the First Supplemental Consenting Holder to the initial holder of the New Note on the purchase date without any further action by the First Supplemental Consenting Holder.

THE FOREGOING PURCHASE RIGHT IN FAVOR OF THE HOLDER OF THE NEW NOTE (THE “REPURCHASE RIGHT”) IS A MATERIAL INDUCEMENT TO SUCH HOLDER’S PARTICIPATION IN AN OVERALL RESTRUCTURING OF THE COMPANY THAT PROVIDES SUBSTANTIAL BENEFIT AND CONSIDERATION TO THE HOLDERS OF EXISTING NOTES. AS NOTED ELSEWHERE, THE NEW NOTE IS SUBORDINATED IN RIGHT OF PAYMENT TO THE NOTES AND NOTE GUARANTEES INITIALLY ISSUED UNDER THE INDENTURE IN THE EVENT OF A BANKRUPTCY OF THE COMPANY. IN THE EVENT A FIRST SUPPLEMENTAL CONSENTING HOLDER OF NOTES FAILS TO COMPLY WITH THE REPURCHASE RIGHT (A “NON-COMPLIANT HOLDER”), THE HOLDER OF THE NEW NOTE SHALL NOT BE SUBORDINATED IN RIGHT OF PAYMENT IN ANY WAY WITH RESPECT TO THE NON-COMPLIANT HOLDER, WHETHER UNDER THIS INDENTURE, THE NOTE GUARANTEES OR OTHERWISE.

On April 9, 2012, an Additional Note was issued pursuant to Section 2.13 and in reliance on Section 4.11(b)(xxiii) in an amount equal to $40.0 million in aggregate principal amount (such Additional Note, the “New Note”). The initial holder of the New

2

Note (which shall include any wholly-owned subsidiary of the initial holder to which the initial holder transfers its interest in such New Note) shall have the right (such right, the “Repurchase Right”), only upon the occurrence of an Event of Default under Section 7.01(a)(vi) or Section 7.01(a)(vii) and only if such holder shall continue to hold the entire initial principal amount of the New Note, to purchase all, but not less than all, other outstanding Notes from the Second Supplemental Consenting Holders thereof at a purchase price equal to the principal amount of such Notes, plus accrued and unpaid interest (including interest accruing on or after the commencement of any proceeding referenced in Section 7.01(a)(vi) or Section 7.01(a)(vii) of the Indenture, whether or not such interest would be allowed in any such proceeding) to, but not including, the date of purchase (the “Purchase Date”). Such purchase shall be consummated upon reasonable notice to the Trustee and the Second Supplemental Consenting Holders of the Notes, except that any such purchase notice to the Trustee and the Second Supplemental Consenting Holders shall be given no later than 15 days before the Purchase Date. Provided that the initial holder of the New Note has caused the deposit of funds with the Trustee sufficient to consummate the purchase of the outstanding Notes on the Purchase Date, the Notes subject to the Repurchase Right shall be deemed automatically transferred by the Second Supplemental Consenting Holder to the initial holder of the New Note on the Purchase Date without any further action by the Second Supplemental Consenting Holder. Notice of the Repurchase Right to the Second Supplemental Consenting Holders of the Notes shall be deemed made upon occurrence of any of the following:

1. Three Business Days following written notice of the Repurchase Right by the Holder of the New Note to DTC;

2. Three Business Days following written notice of the Repurchase Right by the Holder of the New Note to the Trustee; or

3. Written notice of the Repurchase Right is delivered by the Company to the Trustee directing the Trustee to provide notice to the Second Supplemental Consenting Holders of the Notes.

The Company shall provide the notice in subsection 3 above within two Business Days following written notice to the Company by the Holder of the New Note.

THE REPURCHASE RIGHT IS A MATERIAL INDUCEMENT TO SUCH HOLDER’S PARTICIPATION IN AN OVERALL RESTRUCTURING OF THE COMPANY THAT PROVIDES SUBSTANTIAL BENEFIT AND CONSIDERATION TO THE HOLDERS OF EXISTING NOTES. AS NOTED ELSEWHERE, THE NEW NOTE IS SUBORDINATED IN RIGHT OF PAYMENT TO THE NOTES AND NOTE GUARANTEES INITIALLY ISSUED UNDER THE INDENTURE IN THE EVENT OF A BANKRUPTCY OF THE COMPANY OR CERTAIN OF ITS SUBSIDIARIES. IN THE EVENT A SECOND SUPPLEMENTAL CONSENTING HOLDER OF NOTES FAILS TO COMPLY WITH THE REPURCHASE RIGHT (A “NON-COMPLIANT HOLDER”), THE HOLDER OF THE NEW NOTE SHALL NOT BE SUBORDINATED IN RIGHT OF PAYMENT IN ANY WAY WITH RESPECT TO THE NONCOMPLIANT HOLDER, WHETHER UNDER THIS INDENTURE, THE NOTE GUARANTEES OR OTHERWISE.

For purposes of this Section 2.13, “First Supplemental Consenting Holders” shall mean the holders of Notes who consented to the amendments proposed in the Consent Solicitation and Exchange Statement, dated March 29, 2012, but excluding the Second Supplemental Consenting Holders; and “Second Supplemental Consenting Holders” shall mean the holders of Notes who consented to the amendments proposed in the Consent Solicitation and Exchange Statement, dated May 30, 2012.

3

(b) Clause (iii) of the last paragraph of Section 11.02 of the Indenture is hereby amended and restated in its entirety to read as follows:

(iii) has the effect of modifying or amending the provisions of Section 2.13 following the first paragraph of Section 2.13 of this Indenture shall require the consent of Holders of at least 90% in aggregate principal amount of the Notes then outstanding under this Indenture;

(c) The New Note (CUSIP number 44049H AD5) is hereby amended and restated such that:

(i) References in Section 17 of the New Note to “Section 7.01(a)(vi) of the Indenture” will be modified to read “Section 7.01(a)(vi) or Section 7.01(a)(vii) of the Indenture”.

(ii) A new Section 17(e) is added at the end of Section 17, which reads as follows:

“This Section 17 is for the benefit of each Holder of the Original Notes and each Holder of the Original Notes is deemed to have conclusively relied on this Section 17 in acquiring or continuing to hold the Original Notes. This Section 17 is enforceable by the Holders of the Original Notes and may only be amended or modified with the consent of the Holders of at least 75% in aggregate principal amount of the Original Notes then outstanding under the Indenture; provided, however, that the foregoing shall not affect the rights of the Holder of this Note set forth in Section 11.01(j) of the Indenture; and provided further that Section 17(d) may not be amended or modified without the prior written consent of the Holder of this Note.”

ARTICLE II

MISCELLANEOUS

Section 2.01 Instruments To Be Read Together. This Supplemental Indenture is executed as and shall constitute an indenture supplemental to and in implementation of the Indenture, and the Indenture and this Supplemental Indenture shall henceforth be read together. This Supplemental Indenture shall form a part of the Indenture for all purposes, and every Holder of Notes shall be bound hereby and thereby.

Section 2.02 Confirmation. The Indenture as amended and supplemented by this Supplemental Indenture is in all respects confirmed and preserved.

Section 2.03 Terms Defined. Capitalized terms used in this Supplemental Indenture and not otherwise defined herein shall have the meanings assigned to such terms in the Indenture.

Section 2.04 Trust Indenture Act Controls. If any provision of this Supplemental Indenture limits, qualifies or conflicts with another provision that is required to be included in this Supplemental Indenture or the Indenture by the Trust Indenture Act of 1939, as amended, as in force at the date that this Supplemental Indenture is executed, the provisions required by the Trust Indenture Act of 1939 shall control.

Section 2.05 Headings. The headings of the Articles and Sections of this Supplemental Indenture have been inserted for convenience of reference only, and are not to be considered a part hereof and shall in no way modify or restrict any of the terms and provisions hereof.

Section 2.06 Governing Law. The internal law of the State of New York shall govern this Supplemental Indenture without giving effect to applicable principles of conflicts of law to the extent that the application of the laws of another jurisdiction would be required thereby.

Section 2.07 Counterparts. This Supplemental Indenture may be executed in any number of counterparts, each of which so executed shall be deemed to be an original, but all such counterparts shall together constitute but one and the same instrument.

4

Section 2.08 Effectiveness; Termination. The provisions of this Supplemental Indenture will become effective immediately upon its execution by the Trustee in accordance with the provisions of Sections 11.03 of the Indenture; provided, that the amendments to the Indenture set forth in Section 1.01 of this Supplemental Indenture shall become operative as specified in Section 1.01 hereof.

Section 2.09 Acceptance by Trustee. The Trustee accepts the amendments to the Indenture effected by this Supplemental Indenture and agrees to execute the trusts created by the Indenture as hereby amended, but only upon the terms and conditions set forth in the Indenture.

Section 2.10 Responsibility of Trustee. The recitals contained herein shall be taken as the statements of the Company, and the Trustee assumes no responsibility for their correctness. The Trustee makes no representations as to the validity or sufficiency of this Supplemental Indenture.

5

IN WITNESS WHEREOF, the parties hereto have caused this Supplemental Indenture to be duly executed, all as of the date first written above.

[Signature Page to Supplemental Indenture (Second Lien Indenture)]

[Signature Page to Supplemental Indenture (Second Lien Indenture)]

EXHIBIT A

THIS GLOBAL NOTE IS HELD BY THE DEPOSITARY (AS DEFINED IN THE INDENTURE GOVERNING THIS NOTE) OR ITS NOMINEE IN CUSTODY FOR THE BENEFIT OF THE BENEFICIAL OWNERS HEREOF, AND IS NOT TRANSFERABLE TO ANY PERSON UNDER ANY CIRCUMSTANCES EXCEPT THAT (1) THE TRUSTEE MAY MAKE SUCH NOTATIONS HEREON AS MAY BE REQUIRED PURSUANT TO SECTION 2.06 OF THE INDENTURE, (2) THIS GLOBAL NOTE MAY BE EXCHANGED IN WHOLE BUT NOT IN PART PURSUANT TO SECTION 2.06(a) OF THE INDENTURE, (3) THIS GLOBAL NOTE MAY BE DELIVERED TO THE TRUSTEE FOR CANCELLATION PURSUANT TO SECTION 2.11 OF THE INDENTURE AND (4) THIS GLOBAL NOTE MAY BE TRANSFERRED TO A SUCCESSOR DEPOSITARY WITH THE PRIOR WRITTEN CONSENT OF THE ISSUER.

UNLESS AND UNTIL IT IS EXCHANGED IN WHOLE OR IN PART FOR NOTES IN DEFINITIVE FORM, THIS NOTE MAY NOT BE TRANSFERRED EXCEPT AS A WHOLE BY THE DEPOSITARY TO A NOMINEE OF THE DEPOSITARY OR BY A NOMINEE OF THE DEPOSITARY TO THE DEPOSITARY OR ANOTHER NOMINEE OF THE DEPOSITARY OR BY THE DEPOSITARY OR ANY SUCH NOMINEE TO A SUCCESSOR DEPOSITARY OR A NOMINEE OF SUCH SUCCESSOR DEPOSITARY. UNLESS THIS CERTIFICATE IS PRESENTED BY AN AUTHORIZED REPRESENTATIVE OF THE DEPOSITORY TRUST COMPANY (55 WATER STREET, NEW YORK, NEW YORK) (“DTC”), TO THE ISSUER OR ITS AGENT FOR REGISTRATION OF TRANSFER, EXCHANGE OR PAYMENT, AND ANY CERTIFICATE ISSUED IS REGISTERED IN THE NAME OF CEDE & CO. OR SUCH OTHER NAME AS MAY BE REQUESTED BY AN AUTHORIZED REPRESENTATIVE OF DTC (AND ANY PAYMENT IS MADE TO CEDE & CO. OR SUCH OTHER ENTITY AS MAY BE REQUESTED BY AN AUTHORIZED REPRESENTATIVE OF DTC), ANY TRANSFER, PLEDGE OR OTHER USE HEREOF FOR VALUE OR OTHERWISE BY OR TO ANY PERSON IS WRONGFUL INASMUCH AS THE REGISTERED OWNER HEREOF, CEDE & CO., HAS AN INTEREST HEREIN.

THE SECURITY (OR ITS PREDECESSOR) EVIDENCED HEREBY WAS ORIGINALLY ISSUED IN A TRANSACTION EXEMPT FROM REGISTRATION UNDER SECTION 5 OF THE UNITED STATES SECURITIES ACT OF 1933, AS AMENDED (THE “SECURITIES ACT”), AND THE SECURITY EVIDENCED HEREBY MAY NOT BE OFFERED, SOLD OR OTHERWISE TRANSFERRED IN THE ABSENCE OF SUCH REGISTRATION OR AN APPLICABLE EXEMPTION THEREFROM. EACH PURCHASER OF THE SECURITY EVIDENCED HEREBY IS HEREBY NOTIFIED THAT THE SELLER MAY BE RELYING ON THE EXEMPTION FROM THE PROVISIONS OF SECTION 5 OF THE SECURITIES ACT PROVIDED BY RULE 144A THEREUNDER. THE HOLDER OF THE SECURITY EVIDENCED HEREBY AGREES FOR THE BENEFIT OF THE ISSUER THAT (A) SUCH SECURITY MAY BE RESOLD, PLEDGED OR OTHERWISE TRANSFERRED ONLY (i) (a) TO A PERSON WHO IS A QUALIFIED INSTITUTIONAL BUYER (AS DEFINED IN RULE 144A UNDER THE SECURITIES ACT) IN A TRANSACTION MEETING THE REQUIREMENTS OF RULE 144A, (b) IN A TRANSACTION MEETING THE REQUIREMENTS OF RULE 144 UNDER THE SECURITIES ACT, (c) OUTSIDE THE UNITED STATES TO A NON-U.S. PERSON IN A TRANSACTION MEETING THE REQUIREMENTS OF RULE 904 UNDER THE SECURITIES ACT, OR (d) IN ACCORDANCE WITH ANOTHER EXEMPTION FROM THE REGISTRATION REQUIREMENTS OF THE SECURITIES ACT (AND BASED UPON AN OPINION OF COUNSEL IF THE ISSUER SO REQUESTS), (ii) TO THE ISSUER, OR (iii) PURSUANT TO AN EFFECTIVE REGISTRATION STATEMENT AND, IN EACH CASE IN ACCORDANCE WITH ANY APPLICABLE SECURITIES LAWS OF ANY STATE OF THE UNITED STATES OR ANY OTHER APPLICABLE JURISDICTION, AND (B) THE HOLDER WILL, AND EACH SUBSEQUENT HOLDER IS REQUIRED TO, NOTIFY ANY PURCHASER FROM IT OF THE SECURITY EVIDENCED HEREBY OF THE RESALE RESTRICTIONS SET FORTH IN CLAUSE (A) ABOVE. NO REPRESENTATION CAN BE MADE AS TO THE AVAILABILITY OF THE EXEMPTION PROVIDED BY RULE 144 FOR RESALE OF THE SECURITY EVIDENCED HEREBY.

CUSIP:

ISIN:

$

Second Lien Senior Secured Note due 2016

HORIZON LINES, LLC, a Delaware limited liability company, promises to pay to Cede & Co., or registered assigns, the principal sum set forth on the Schedule of Increases or Decreases in Global Note attached hereto on October 15, 2016.

Interest Payment Dates: April 15 and October 15

Interest Record Dates: April 1 and October 1

Additional provisions of this Note are set forth on the other side of this Note.

2

IN WITNESS WHEREOF, the parties have caused this instrument to be duly executed.

[Signature Page to Second Lien Senior Secured Note]

This is one of the Notes referred to in the within mentioned Indenture:

Dated:                     , 2012

[Signature Page to Second Lien Senior Secured Note]

Second Lien Senior Secured Note Due 2016

Capitalized terms used herein shall have the meanings assigned to them in the Indenture referred to below unless otherwise indicated.

1. HORIZON LINES, LLC, a Delaware limited liability company (the “Issuer”), promises to pay interest on the principal amount of this Note at the rate per annum set forth below from the date of issuance until maturity and shall pay the Additional Interest, if any, payable pursuant to the Registration Rights Agreement referred to below. The Issuer will pay interest and Additional Interest, if any, semi-annually in arrears on April 15 and October 15 of each year, or if any such day is not a Business Day, on the next succeeding Business Day (each, an “Interest Payment Date”). Interest on the Notes will accrue from the most recent date to which interest has been paid or, if no interest has been paid, from the Issue Date; provided that the first Interest Payment Date shall be April 15, 2012. The Issuer will pay interest (including post-petition interest in any proceeding under any Bankruptcy Law) on overdue principal and premium, if any, from time to time on demand at the rate then in effect to the extent lawful; it will pay interest (including post-petition interest in any proceeding under any Bankruptcy Law) on overdue installments of interest and Additional Interest, if any (without regard to any applicable grace periods), from time to time on demand at the same rate to the extent lawful. Interest will be computed on the basis of a 360-day year comprised of twelve 30-day months.

Cash Interest (as defined below) on the Notes will accrue at a rate of 13.00% per annum. PIK Interest (as defined below) on the Notes will accrue at a rate of 15.00% per annum. Partial PIK Interest (as defined below) on the Notes will accrue at a rate of 14.00% per annum. Following an increase in the principal amount of the outstanding Global Notes as a result of a PIK Payment, the relevant Notes will bear interest on such increased principal amount from and after the date of such PIK Payment. Any PIK Notes issued in certificated form will be dated as of the applicable Interest Payment Date and will bear interest from and after such date.

2. METHOD OF PAYMENT.

For any interest payment period the Issuer may, at its option elect to pay interest on the Notes:

(i) entirely in cash (“Cash Interest”);

(ii) entirely by increasing the principal amount of the outstanding Notes or by issuing PIK Notes (“PIK Interest”); or

(iii) on 50% of the outstanding principal amount of the Notes in cash and on 50% of the outstanding principal amount by increasing the principal amount of the outstanding Notes or by issuing PIK Notes (“Partial PIK Interest”).

The Issuer must elect the form of interest payment with respect to each interest period by delivering a written notice to the Trustee prior to the beginning of such interest period. The Trustee shall promptly deliver a corresponding written notice to the Holder of this Note. In the absence of such an election for any interest period, interest on this Note shall be payable according to the election for the previous interest period. Interest for the first interest payment period commencing on the Issue Date shall be payable entirely by PIK Interest.

The Issuer will pay interest on the Notes (except defaulted interest) and Additional Interest, if any, to the Persons who are registered Holders of Notes at the close of business on the April 1 and October 1 Interest Record Date (whether or not a Business Day), as the case may be, immediately preceding the Interest Payment Date, even if such Notes are cancelled after such Interest Record Date and on or before such Interest Payment Date, except as provided in Section 2.12 of the Indenture with respect to defaulted interest. The Notes will be payable as to principal, premium and Additional Interest, if any, and interest at the office or agency of the Issuer of the Issuer maintained for such purpose.

At the option of the Issuer, payment of Cash Interest and Additional Interest, if any, may be made by check mailed to the Holders at their addresses set forth in the register of Holders, provided that payment by wire transfer of

5

immediately available funds will be required with respect to principal of and Cash Interest, premium and Additional Interest, if any, on all Global Notes and all other Notes the Holders of which shall have provided wire transfer instructions to the Issuer or the Paying Agent. Payments of principal, Cash Interest, premium and Additional Interest shall be in such coin or currency of the United States of America as at the time of payment is legal tender for payment of public and private debts.

PIK Interest on the Notes will be payable (x) with respect to Notes represented by one or more Global Notes registered in the name of, or held by, The Depository Trust Company (“DTC”) or its nominee on the relevant Interest Record Date, by increasing the principal amount of the outstanding Global Note by an amount equal to the amount of PIK Interest for the applicable interest period (rounded up to the nearest $1,000) (or, if necessary, pursuant to the requirements of DTC or otherwise, to authenticate new Global Notes executed by the Issuer with such increased principal amounts) and (y) with respect to Notes represented by Definitive Notes, by issuing PIK Notes in the form of Definitive Notes that are not Global Notes in an aggregate principal amount equal to the amount of PIK Interest for the applicable period (rounded up to the nearest whole dollar), and the Trustee will, at the request of the Issuer, authenticate and deliver such PIK Notes for original issuance to the Holders.

In the event that the Issuer elects to pay Partial PIK Interest for any interest period, each Holder will be entitled to receive Cash Interest in respect of 50% of the principal amount of the Notes held by such Holder on the relevant Interest Record Date and PIK Interest in respect of 50% of the principal amount of the Notes held by such Holder on the relevant Interest Record Date, in each case, as provided above.

All Notes issued pursuant to a PIK Payment will mature on October 15, 2016 and will be governed by, and subject to the terms, provisions and conditions of, the Indenture and shall have the same rights and benefits as all other Notes (except as specifically provided in the Indenture). Any certificated PIK Notes will be issued with the description PIK on the face of such PIK Note.

3. TRUSTEE; PAYING AGENT AND REGISTRAR. U.S. Bank National Association, the Trustee under the Indenture, will act as Paying Agent and Registrar. The Issuer may change any Paying Agent or Registrar without notice to any Holder. None of the Issuer or any of its Affiliates may act in any such capacity.

4. INDENTURE AND SECURITY DOCUMENTS. The Issuer issued the Notes under an Indenture, dated as of October 5, 2011 (the “Indenture”), among the Issuer, the Guarantors party thereto and the Trustee. This Note is one of a duly authorized issue of Notes of the Issuer. The terms of the Notes include those stated in the Indenture. The Notes are subject to all such terms, and Holders are referred to the Indenture for a statement of such terms. To the extent any provision of this Note conflicts with the express provisions of the Indenture, the provisions of the Indenture shall govern and be controlling. Following the Issue Date, the Notes and the related Note Guarantees are secured obligations of the Issuer and the relevant Guarantors. The Notes and the related Note Guarantees are secured by a pledge of the Collateral pursuant to the Security Documents referred to in the Indenture. The Note Liens, which secure the Notes and the related Note Guarantees, and the ABL Liens are subject to the terms of the Intercreditor Agreement. Each Holder, by accepting a Note agrees that the Note Liens and the ABL Liens are subject to the terms of the Intercreditor Agreement. The Holders, by accepting a Note, hereby authorize and direct the Trustee and the Collateral Agent to enter into the Intercreditor Agreement on behalf of the Holders and agree that the Holders shall comply with the provisions of the Intercreditor Agreement applicable to them in their capacities as such to the same extent as if the Holders were parties thereto. The Indenture does not limit the aggregate principal amount of Notes that may be issued thereunder.

5. OPTIONAL REDEMPTION.

(a) Prior to October 15, 2013, the Notes will not be subject to redemption at the option of the Issuer. The Notes are subject to redemption, at the option of the Issuer, in whole or in part, at any time on or after October 15, 2013, upon not less than 30 nor more than 60 days’ notice at the redemption prices (expressed as percentages of the principal amount to be redeemed) set forth below, plus accrued and unpaid interest, if any, to, but not including, the redemption date (subject to the rights of Holders of record on the relevant regular record date to receive interest due on an Interest Payment Date), if redeemed during the 12-month period beginning on October 15 of the years indicated:

6

(b) Any notice of any redemption may be given prior to the redemption of any Notes, and any such redemption or notice may, at the Issuer’s discretion, be subject to one or more conditions precedent, including, but not limited to, completion of a securities issuance or other corporate transaction.

6. MANDATORY REDEMPTION. The Issuer will not be required to make any mandatory redemption or sinking fund payments with respect to the Notes. The Issuer may at any time and from time to time purchase Notes in the open market, in privately negotiated transactions or otherwise.

7. REPURCHASE RIGHT OF INITIAL HOLDER OF NEW NOTE. This Note is subject to the Repurchase Right as set forth in Section 2.13 of the Indenture. Holders of this Note are deemed to be Second Supplemental Consenting Holders.

8. OFFERS TO REPURCHASE.

(a) Upon the occurrence of a Change of Control, the Issuer shall be required to make a Change of Control Offer in accordance with Section 4.16 of the Indenture.

(b) In accordance with Section 4.12 of the Indenture, the Issuer will be required to offer to purchase Notes upon the occurrence of certain events.

9. DENOMINATIONS, TRANSFER, EXCHANGE. The Notes are in fully registered form only, without coupons, in minimum denominations of $1.00 and integral multiples of $1.00 in excess thereof. A Holder shall register the transfer or exchange of Notes in accordance with the Indenture. The Registrar may require a holder, among other things, to furnish appropriate endorsements and transfer documents and to pay certain transfer taxes or similar governmental charges payable in connection therewith as permitted by the Indenture. The Registrar need not register the transfer or exchange of any Notes during a period beginning 15 days before the mailing of a redemption notice for any Notes or portions thereof selected for redemption.

10. PERSONS DEEMED OWNERS. The registered Holder of a Note may be treated as its owner for all purposes.

11. AMENDMENT, SUPPLEMENT AND WAIVER. The Indenture, the Guarantees or the Notes may be amended or supplemented as provided in Article 11 of the Indenture and Events of Default may be waived as provided in Article 7 of the Indenture.

12. DEFAULTS AND REMEDIES. If an Event of Default occurs (other than an Event of Default relating to certain events of bankruptcy, insolvency or reorganization of the Issuer) and is continuing, the Trustee or the Holders of at least 25% in principal amount of the outstanding Notes, in each case, by notice to the Issuer, may declare the principal of, premium, if any, and accrued but unpaid interest on all the Notes to be due and payable. If an Event of Default relating to certain events of bankruptcy, insolvency or reorganization of the Issuer or certain Restricted Subsidiaries occurs, the principal of, premium, if any, and interest on all the Notes shall become immediately due and payable without any declaration or other act on the part of the Trustee or any Holders. Under certain circumstances, the Holders of a majority in principal amount of the outstanding Notes may rescind any such acceleration with respect to the Notes and its consequences.

7

13. AUTHENTICATION. This Note shall not be entitled to any benefit under the Indenture or be valid or obligatory for any purpose until authenticated by the manual signature of the Trustee or an authenticating agent.

14. ADDITIONAL RIGHTS OF HOLDERS OF RESTRICTED GLOBAL NOTES AND RESTRICTED DEFINITIVE NOTES. In addition to the rights provided to Holders of Notes under the Indenture, Holders of Restricted Global Notes and Restricted Definitive Notes shall have all the rights set forth in the Registration Rights Agreement, including the right to receive Additional Interest (as defined in the Registration Rights Agreement).

15. GOVERNING LAW. THE LAWS OF THE STATE OF NEW YORK SHALL GOVERN AND BE USED TO CONSTRUE THE INDENTURE, THE NOTES AND THE GUARANTEES.

16. CUSIP AND ISIN NUMBERS. Pursuant to a recommendation promulgated by the Committee on Uniform Security Identification Procedures, the Issuer has caused CUSIP and ISIN numbers to be printed on the Notes and the Trustee may use CUSIP and ISIN numbers in notices of redemption as a convenience to Holders. No representation is made as to the accuracy of such numbers either as printed on the Notes or as contained in any notice of redemption and reliance may be placed only on the other identification numbers placed thereon.

17. REFERENCE TO INDENTURE AND OTHER RELATED DOCUMENTS. Reference is hereby made to the Indenture, the Security Agreement, the Intercreditor Agreement and other Note Documents (copies of which are on file at the Corporate Trust Office of the Trustee) and all indentures and agreements supplemental thereto for a description of the rights thereunder of the Holders of the Notes, the nature and extent of the security therefor, the rights, duties, protections and immunities of the Trustee and the rights and obligations of the Issuer and the Note Guarantors thereunder, to all the provisions of which the Holder, by acceptance hereof, assents and agrees.

The Issuer will furnish to any Holder upon written request and without charge a copy of the Indenture and/or the Registration Rights Agreement. Requests may be made to the Issuer at the following address:

Horizon Lines, LLC

4064 Colony Road

Suite 200 Charlotte, North Carolina 28211 Attention:

General Counsel

8

ASSIGNMENT FORM

To assign this Note, fill in the form below:

(I) or (we) assign and transfer this Note to:

(Insert assignee’s legal name)

(Insert assignee’s Soc. Sec. or tax I.D. no.)

(Print or type assignee’s name, address and zip code)

and irrevocably appoint;                                                                                                                                                                                     

to transfer this Note on the books of the Issuer. The agent may substitute another to act for him.

Dated: ________________

Signature Guarantee*:________________________________________________

9

OPTION OF HOLDER TO ELECT PURCHASE

If you want to elect to have this Note purchased by the Issuer pursuant to Section 4.12 or 4.16 of the Indenture, check the appropriate box below:

¨ Section 4.12         ¨ Section 4.16

If you want to elect to have only part of this Note purchased by the Issuer pursuant to Section 4.12 or Section 4.16 of the Indenture, state the amount you elect to have purchased:

$___________

Date: ___________________

Signature Guarantee*:__________________________________

10

SCHEDULE OF INCREASES OR DECREASES IN GLOBAL NOTE*

The initial outstanding principal amount of this Global Note is $107,916,651. The following exchanges of a part of this Global Note for an interest in another Global Note or for a Definitive Note, or exchanges of a part of another Global or Definitive Note for an interest in this Global Note, have been made:

11

NOTATION OF GUARANTEE

For value received, each Guarantor (which term includes any successor Person under the Indenture) has, jointly and severally, unconditionally guaranteed, to the extent set forth in the Indenture and subject to the provisions in the Indenture dated as of October 5, 2011 (the “Indenture”) among Horizon Lines, LLC (the “Issuer”), the Guarantors party thereto and U.S. Bank National Association, as trustee (the “Trustee”) and collateral agent (the “Collateral Agent”), (a) the due and punctual payment of the principal of, premium and additional interest, if any, and interest on, the Notes, whether at maturity, by acceleration, redemption or otherwise, the due and punctual payment of interest on overdue principal of and interest on the Notes, if any, if lawful, and the due and punctual performance of all other obligations of the Issuer to the Holders or the Trustee or Collateral Agent all in accordance with the terms of the Indenture and other Note Documents and (b) in case of any extension of time of payment or renewal of any Notes or any of such other obligations, that the same will be promptly paid in full when due or performed in accordance with the terms of the extension or renewal, whether at stated maturity, by acceleration or otherwise. The obligations of the Guarantors to the Holders of Notes and to the Trustee and Collateral Agent pursuant to the Note Guarantee, the Indenture and other Note Documents are expressly set forth in Article 10 of the Indenture and reference is hereby made to the Indenture for the precise terms of the Note Guarantee.

Capitalized terms used but not defined herein have the meanings given to them in the Indenture.

HORIZON LINES, LLC

HORIZON LINES HOLDING CORP.

HAWAII STEVEDORES, INC.

HORIZON LINES OF PUERTO RICO, INC.

HORIZON LINES OF ALASKA, LLC

HORIZON LINES OF GUAM, LLC

HORIZON LINES VESSELS, LLC

H-L DISTRIBUTION SERVICE, LLC

HORIZON LOGISTICS, LLC

[Signature Page to Form of Notation of Guarantee]