Exhibit 4.4

SUPPLEMENTAL INDENTURE

THIS SUPPLEMENTAL INDENTURE (this “Supplemental Indenture”) is dated as of October 5, 2011, and has been entered into by and between Horizon Lines, Inc., a Delaware corporation, having its principal office at 4046 Colony Road, Suite 200, Charlotte, North Carolina 2821, (the “Company”), and The Bank of New York Mellon Trust Company, N.A., as trustee (the “Trustee”).

RECITALS

WHEREAS, the Company and the Trustee previously entered into that certain indenture dated as of August 8, 2007 (the “Indenture”), providing for the issuance of the Company’s 4.25% Senior Convertible Notes due 2012 (the “Notes”);

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

WHEREAS, Section 8.02 of the Indenture provides that the Company, when authorized by a Board Resolution, and the Trustee, upon receipt of a Company Request and an Opinion of Counsel, 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, with written consent of the Holders of not less than a majority in principal amount of the outstanding Notes (including without limitation, consents obtained in connection with a purchase of, or tender offer or exchange offer for Notes), by the act of said Holders delivered to the Company and the Trustee;

WHEREAS, the Company has offered to exchange shares of its common stock or warrants or redemption notes, as the case may be, and its 6.00% Series A Convertible Senior Secured Notes due 2017 and 6.00% Series B Mandatorily Convertible Senior Secured Notes for any and all outstanding Notes upon the terms and subject to the conditions set forth in the Registration Statement on Form S-4 originally filed with the Securities and Exchange Commission on August 26, 2011, as the same may be amended, supplemented or modified (the “Prospectus”) and the Schedule TO originally filed with the Securities and Exchange Commission on August 26, 2011, as may be amended supplemented or modified;

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 (the “Proposed Amendments”);

WHEREAS, all acts and requirements necessary to make this Supplemental Indenture the legal, valid and binding obligation of the Company 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 Amendments to Articles 5, 7 and 10. Upon written notification to the Trustee by the Company that it has accepted for exchange any and all of the Notes validly tendered on or prior to 5:00 p.m., New York City time, on October 3, 2011 pursuant to the Prospectus and any amendments, modifications or supplements thereto, then automatically (without further act by any person), with respect to the Notes:

(a) The Company shall be released from the restrictions or its obligations, as the case may be, under the following sections of the Indenture:

(b) Failure to comply with the terms of any of the foregoing Sections of the Indenture shall no longer constitute a Default or an Event of Default under the Indenture and shall no longer have any other consequence under the Indenture.

(c) The occurrence of the events of default described in Section 5.01 (d), (e), (f), (g), (h), (i) and (j) shall no longer constitute Events of Default, shall be deleted in their entirety, including all references therein.

(d) All definitions set forth in Section 1.01 of the Indenture that relate to defined terms used solely in covenants or sections deleted hereby are deleted in their entirety.

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 said 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.

2

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.

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 8.02 and 8.04 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.

3

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

4