Exhibit 4.1

FIRST SUPPLEMENTAL INDENTURE

(TO FIRST LIEN INDENTURE)

THIS FIRST SUPPLEMENTAL INDENTURE (this “Supplemental Indenture”) is dated as of April 9, 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 “Issuer”), 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 Issuer, the Guarantors and the Trustee previously entered into that certain indenture dated as of October 5, 2011 (the “Indenture”), providing for the issuance of the Issuer’s 11.00% First Lien Senior Secured Notes due 2016 (the “Notes”);

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

WHEREAS, Section 11.02 of the Indenture provides that the Issuer 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 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 Issuer and the Trustee;

WHEREAS, the Issuer conducted a consent solicitation (the “Consent Solicitation”), pursuant to which $187,598,000 in aggregate principal amount, representing 83.38% of the outstanding Notes consented to the Proposed Amendments (as defined in the Consent Solicitation Statement with respect to the Notes, dated March 29, 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, the Issuer has been authorized by Board Resolution to enter into this Supplemental Indenture;

WHEREAS, the Issuer 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 Issuer and the Guarantors have been done; and

WHEREAS, the Issuer 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 Issuer and the Trustee hereby agree as follows:

ARTICLE I

AMENDMENTS TO INDENTURE

Section 1.01 Amendments to the Indenture.

(a) Clause (39) of the definition of Permitted Liens in Section 1.01 of the Indenture is hereby amended and restated in its entirety to read as follows:

(39) Liens (whose priority shall be governed by the Intercreditor Agreement) held by the Collateral Agent securing (i) the $100.0 million aggregate principal amount of Second-Lien Notes (and the Guarantees by the Guarantors in respect thereof) issued on the Issue Date and additional Second-Lien Notes (and Guarantees by the Guarantors in respect thereof) issued after the Issue Date as “PIK Interest” (as defined in the Second-Lien Notes Indenture in effect on the Issue Date) on such Second-Lien Notes or on any Second-Lien Notes issued as such “PIK Interest” and all related obligations and (ii) Convertible Notes (and the Guarantees by the Guarantors in respect thereof) in an aggregate principal amount of up to $280.0 million (less the aggregate principal amount of any Convertible Notes that have been converted in a “Mandatory Conversion” pursuant to the terms thereof) and additional Convertible Notes (and Guarantees by the Guarantors in respect thereof) issued after the Issue Date as “PIK Interest” (as defined in the Convertible Notes Indenture in effect on the Issue Date) on such Convertible Notes or on any Convertible Notes issued as such “PIK Interest” and all related obligations; and

(b) Clause (b)(v) of Section 4.11 of the Indenture is hereby amended and restated in its entirety to read as follows:

(v) the incurrence by the Parent or any of its Restricted Subsidiaries of Permitted Refinancing Indebtedness in exchange for, or the net proceeds of which are used to extend, renew, refund, refinance, replace, defease or discharge any Indebtedness (other than intercompany Indebtedness) that was permitted to be incurred under Section 4.11(a) or clause (ii), (iii), (iv), (v), (xix) or (xxiii) of this Section 4.11(b);

(c) The second sentence of clause (d) of Section 4.11 of the Indenture is hereby amended and restated in its entirety to read as follows:

The accrual of interest, the accretion or amortization of original issue discount, the payment of interest on any Indebtedness in the form of additional Indebtedness with the same terms, including PIK Interest, the reclassification of preferred stock as Indebtedness due to a change in accounting principles, and the payment of dividends on Disqualified Stock in the form of additional shares of the same class of Disqualified Stock will not be deemed to be an incurrence of Indebtedness or an issuance of Disqualified Stock for purposes of this covenant; provided, in each such case, that the amount of any such accrual, accretion or payment is included in Fixed Charges of Parent as accrued.

(d) Section 4.20 of the Indenture is hereby amended and restated in its entirety to read as follows:

Except for Liens permitted by clauses (1)(ii) and (35) of the definition of “Permitted Liens,” the Issuer and the Guarantors may not create any Lien on any of the Collateral with a priority that is lower than that of any ABL Lien, Note Lien, Second-Lien Note Lien or Convertible Note Lien yet also higher than that of any ABL Lien, Note Lien, Second-Lien Note Lien or Convertible Note Lien (other than an ABL Lien, a Note Lien, a Second-Lien Note Lien or Convertible Note Lien).

2

(e) Section 16.10 of the Indenture is hereby amended and restated in its entirety to read as follows:

The Issuer and the Guarantors will furnish to the Collateral Agent and the Trustee (x) immediately prior to the Issue Date and (y) on April 15 of each year, so long as any of the Notes are outstanding (unless defeased in accordance with Article 14), beginning with April 15, 2012, an Opinion of Counsel, dated as of such date, stating that, in the opinion of such counsel, all such action has been taken with respect to the recording, filing, re-recording and refiling of Liens under the Security Documents on Article 9 Collateral, on collateral consisting of Vessels with respect to which Liens are perfected by recording a mortgage with the National Vessel Documentation Center of the United States Coast Guard, and on collateral with respect to which Liens are perfected by filings with the United States Patent and Trademark Office and the United States Copyright Office, as is necessary to maintain the perfection of such Liens, and reciting the details of such action, or stating that in the opinion of such counsel no such action is required to maintain the perfection of such Liens. For purposes of the foregoing, the term “Article 9 Collateral” shall mean Collateral with respect to which a Lien thereon may be perfected by the filing of a UCC-1 financing statement pursuant to the Uniform Commercial Code as adopted in the jurisdiction of organization of the Issuer or the applicable Guarantor.

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.

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.

3

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.

4

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 (First Lien Indenture)]

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