FIRST SUPPLEMENTAL INDENTURE (TO SECOND LIEN INDENTURE)

Exhibit 4.2

FIRST SUPPLEMENTAL INDENTURE

(TO SECOND 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 “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 (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 $100,000,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;

WHEREAS, the Company conducted a consent solicitation (the “Consent Solicitation”), pursuant to which $88,323,000 in aggregate principal amount, representing 88.32% of the outstanding Notes, consented to the Proposed Amendments (as defined in the Consent Solicitation and Exchange 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, 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 Consent Only Amendment (as defined in the Statement) (the “PIK Amended Notes”);

WHEREAS, Section 11.01 of the Indenture provides that the Company may make certain amendments to the Indenture without the consent of the Noteholders;

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 PIK Amended Notes. The PIK Amended Notes issued to holders of Notes who gave their consent to the Proposed Amendments, which incorporate the Consent Only Amendments, will be substantially in the form of Exhibit A hereto.

Section 1.02 Amendments to the Indenture

(a) The third sentence of the first paragraph of back face of the Note is hereby amended and restated in its entirety to read as follows:

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 for Notes issued prior to October 15, 2012 shall be April 15, 2012.

(b) The first sentence of clause (c) of Section 2.01 of the Indenture is hereby amended and restated in its entirety to read as follows:

Additional Notes ranking pari passu with the other Notes may be created and issued from time to time by the Issuer without notice to or consent of the Holders and shall be consolidated with and form a single class with the other Notes and shall have the same terms as to status, redemption or otherwise as the other Notes; provided that the Issuer’s ability to issue Additional Notes shall be subject, among other things, to the Issuer’s compliance with Section 4.11 hereof; provided further that in connection with the payment of PIK Interest, the Issuer may, without the consent of the Holders (and without regard to any restrictions or limitations set forth in Section 4.11 hereof), increase the outstanding principal amount of the Notes or issue PIK Notes; provided further that, notwithstanding this Section 2.01(c), the Issuer may issue Additional Notes in accordance with Section 2.13.

(c) The first sentence of Section 2.13 of the Indenture is hereby amended and restated in its entirety to read as follows:

The Issuer may, without the consent of the Noteholders, issue additional Notes hereunder (i) with the same terms, and if permissible as a “qualified reopening” for U.S. federal income tax purposes, with the same CUSIP number as the Notes initially issued hereunder or (ii) with terms that provide that such additional Notes will be subordinated to the Notes initially issued hereunder, including with respect to lien priority upon the occurrence of an Event of Default under Section 7.01(a)(vi), but otherwise with the same terms as the Notes initially issued hereunder and with a different CUSIP number as the Notes initially issued hereunder, in each case in an unlimited aggregate principal amount, which will form the same series with the Notes initially issued hereunder.

(d) Section 2.13 of the Indenture is hereby amended to add the following paragraphs after the first paragraph of Section 2.13, which shall only be binding on those holders of Notes who gave their consent to the Proposed Amendments:

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,

2

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 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 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 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 Holder to the initial holder of the New Note on the purchase date without any further action by the 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 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.

(e) 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);

(f) 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 First-Lien Notes Collateral Agent securing (i) the $225.0 million aggregate principal amount of First-Lien Notes (and the Guarantees by the Guarantors in respect thereof) issued on the Issue Date 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.

(g) 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

3

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.

(h) 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, First-Lien Note Lien or Convertible Note Lien yet also higher than that of any ABL Lien, Note Lien, First-Lien Note Lien or Convertible Note Lien (other than an ABL Lien, a Note Lien, a First-Lien Note Lien or Convertible Note Lien).

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

In addition, any amendment to, or waiver of, the provisions of this Indenture, the Notes, the Note Guarantees or any Security Document that (i) has the effect of releasing, except as otherwise permitted pursuant to this Indenture, all or substantially all of the Collateral from the Note Liens shall require the consent of the Holders of at least 90% in aggregate principal amount of the Notes then outstanding under this Indenture, (ii) releases, except as otherwise permitted pursuant to this Indenture, any Collateral from the Note Liens shall require the consent of Holders of at least 75% in aggregate principal amount of the Notes then outstanding under this Indenture or (iii) 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 this Indenture.

(j) 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.

4

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.

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