Exhibit 4.3

FIRST SUPPLEMENTAL INDENTURE

(TO CONVERTIBLE 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, Inc., a Delaware corporation, 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 6.00% Series A Convertible Senior Secured Notes due 2017 (the “Series A Notes”) and 6.00% Series B Mandatorily Convertible Senior Secured Notes (the “Series B Notes” and, together with the Series A Notes, the “Notes”);

WHEREAS, Series A Notes in the aggregate principal amount of $178,781,456 and Series B Notes in the aggregate principal amount of $49,661,522 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 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, 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 $197,084,866 in aggregate principal amount of Notes, representing 86.27% of the outstanding Notes, which were treated as a single class for the purposes of the Consent Solicitation, 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, Series A Notes held by Holders who gave their consent to the Proposed Amendments (as definite in the Statement), will trade under a new CUSIP number to reflect the PIK Interest Amendment (as defined in the Statement) (the “Series A PIK Amended Notes”) and Series B Notes held by Holders who gave their consent to the Proposed Amendments will trade under a new CUSIP number to reflect the PIK Interest Amendment (the “Series B PIK Amended Notes” and, together with the Series A PIK Amended Notes, the “PIK Amended 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 PIK Amended Notes. The PIK Amended Notes issued to holders of Notes who gave their consent to the Proposed Amendments will be substantially in the form of Exhibit A and Exhibit B hereto, as applicable.

Section 1.02 Amendments to the Indenture.

(a) The definition of “Conversion Date” in Section 1.01 of the Indenture is hereby amended and restated in its entirety to read as follows:

“Conversion Date” means (i) in the case of the Series A Notes, the date on which a Holder satisfies all of the applicable requirements for conversion set forth in Section 14.02 and (ii) in the case of the Series B Notes, the date such Notes are converted in accordance with Section 14.04 or the date that the Holder satisfies all of the applicable requirements for conversion set forth in Section 14.02.

(b) 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 First-Lien Notes issued on the Issue Date (and the guarantees by the guarantors in respect thereof) and all related obligations, (ii) the Second-Lien Notes issued on the Issue Date (and the guarantees by the guarantors in respect thereof) and additional Second-Lien Notes (and the 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

(c) Section 1.01 of the Indenture is hereby amended to add the following definitions immediately after the definition of “Person”:

“PIK Interest” has the meaning set forth in Exhibit A and Exhibit B attached to the Supplemental Indenture, dated as of April 9, 2012.

“PIK Notes” means Additional Notes or Series B Notes, as the case may be, issued under this Indenture on the same terms and conditions as the Notes in connection with a PIK Payment. For purposes of this Indenture, all references to “PIK Notes” shall include the Related PIK Notes.

“PIK Payment” means an interest payment with respect to the Notes made by increasing the outstanding principal amount of the Notes or issuing PIK Notes.

(d) Section 1.01 of the Indenture is hereby amended to add the following definitions immediately after the definition of “Registration Rights Agreement”:

“Related PIK Notes” means, with respect to a Note, (i) each PIK Note issued in connection with a PIK Payment on such Note and (ii) each additional PIK Note issued in connection with a PIK Payment on a Related PIK Note with respect to such Note.

2

(e) Section 2.04 of the Indenture is hereby amended to add the following paragraphs immediately following the last paragraph:

At any time, and from time to time, the Trustee shall, upon receipt of a Company Order, authenticate and deliver any Additional Notes or PIK Notes (or increases in the principal amount of any Notes) as a result of a PIK Payment, for an aggregate principal amount specified in such Company Order for such Additional Notes or PIK Notes (or increases in the principal amount of such Notes). Such Company Order shall specify the amount of the Notes to be authenticated and, in the case of any issuance of Additional Notes, shall certify that such issuance is in compliance with Section 4.11 hereof.

On any Interest Payment Date on which the Issuer pays PIK Interest with respect to a Global Note, the Trustee, upon receipt of a Company Order, shall increase the principal amount of such Global Note by an amount equal to the interest payable, rounded up to the nearest $1.00, for the relevant interest period on the principal amount of such Global Note as of the relevant Record Date, for such Interest Payment Date, to the credit of the Holders on such Record Date, pro rata in accordance with their interests, and an adjustment shall be made on the books and records of the Trustee (if it is then the Custodian for such Global Note) with respect to such Global Note, by the Trustee or the Custodian, to reflect such increase. On any Interest Payment Date on which the Issuer pays PIK Interest by issuing definitive PIK Notes, the principal amount of any such PIK Notes issued to any Holder, for the relevant interest period as of the relevant Interest Record Date for such Interest Payment Date, shall be rounded up to the nearest $1.00.

(f) Section 2.10 of the Indenture is hereby amended to add the following paragraph immediately following the last paragraph:

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. The Notes offered by the Issuer, the PIK Notes and any Additional Notes subsequently issued under this Indenture will be treated as a single class for all purposes under this Indenture, including, among other things, waivers, amendments, redemptions and offers to purchase. Unless the context requires otherwise, references to “Notes” for all purposes under this Indenture include any PIK Notes and Additional Notes that are actually issued, and references to “principal amount” of the Notes includes any increases in the principal amount of the outstanding Notes as a result of a PIK Payment.

(g) Section 4.01 of the Indenture is hereby amended to add the following sentence immediately following the last sentence:

PIK Interest shall be considered paid on the date due if the Trustee is directed on or prior to such date to issue PIK Notes or increase the principal amount of the applicable Notes, in each case in an amount equal to the amount of the applicable PIK Interest.

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

(5) the incurrence by the Company 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 (2), (3), (4), (5), (19) or (23) of this Section 4.11(b);

3

(i) 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 the Company as accrued.

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

(k) Section 14.01 and Section 14.02 of the Indenture are hereby amended and restated in their entirety to read as follows:

Section 14.01 Right to Convert Series A Notes and Series B Notes

(a) Subject to and upon compliance with the provisions of this Indenture, each Holder shall have the right, at such Holder’s option, to convert the principal amount of any Series A Notes at the Series A Conversion Rate then in effect and any Series B Notes at the Series B Conversion Rate then in effect, any time prior to the close of business on the third Scheduled Trading Day immediately preceding the Maturity Date.

(b) Series A Notes and Series B Notes may not be converted after the close of business on the third Scheduled Trading Day immediately preceding the Maturity Date.

(c) A Holder may convert fewer than all of such Holder’s Series A Notes or Series B Notes so long as the principal amount of Series A Notes or Series B Notes, as applicable, to be converted is an integral multiple of $1.00 and all Series A Notes and Series B Notes, as applicable, remaining that are held by such Holder are in a minimum denomination of $1.00.

(d) If Series A Notes or Series B Notes are converted after the close of business on an Interest Record Date, holders of such Notes at the close of business on such Interest Record Date will receive the interest and Supplementary Interest, if any, payable on such Series A Notes or Series B Notes, as applicable, on the corresponding Interest Payment Date notwithstanding the conversion.

Section 14.02 Conversion Procedures for Series A Notes and Series B Notes.

(a) Each Series A Note and Series B Note shall be convertible at the office of the Conversion Agent and, if applicable, in accordance with the procedures of the Depositary.

4

(b) In order to exercise the conversion privilege with respect to any interest in a Global Note, the Holder must comply with the Depositary’s procedures for converting a beneficial interest in a Global Note and, if required, pay all transfer taxes pursuant to Section 14.10, if any. In order to exercise the conversion privilege with respect to any certificated Notes, the Holder of any such Notes to be converted, in whole or in part, shall:

(i) complete and manually sign the conversion notice on the back of the Note, which may be amended by the Holder to be conditional upon certain events being satisfied (the “Conversion Notice”), or facsimile of the Conversion Notice and deliver such notice, which is irrevocable, to the Conversion Agent;

(ii) surrender the Note to the Conversion Agent;

(iii) if required, furnish appropriate endorsements and transfer documents; and

(iv) if required, pay all transfer or similar taxes.

The Trustee will, as promptly as possible, provide the Company with notice of any conversion exercised by Holders of which a Responsible Officer becomes aware.

Once a Note is converted in accordance with this Section 14.02, such Note shall no longer have the benefit of any security interest in the Collateral.

(c) Each Conversion Notice shall state the name or names (with address or addresses) in which any certificate or certificates for shares of Common Stock or Warrants which shall be issuable on such conversion shall be issued. All Notes surrendered for conversion shall, unless any shares of Common Stock issuable on conversion are to be issued in the same name as the registration of such Notes, be duly endorsed by, or be accompanied by instruments of transfer in form satisfactory to the Company duly executed by, the Holder or his duly authorized attorney.

(d) In case any Notes shall be surrendered for partial conversion, the Company shall execute and the Trustee shall, upon receipt of a Company Order, authenticate and deliver to the Holder of the Notes so surrendered, without charge to such Holder, new Notes in authorized denominations in an aggregate principal amount equal to the unconverted portion of the surrendered Notes.

(e) Each conversion shall be deemed to have been effected as to any Notes (or portion thereof) surrendered for conversion on the relevant Conversion Date, and with respect to any shares of Common Stock or Warrants that are issuable upon such conversion, the Person in whose name the certificate or certificates for such shares of Common Stock will be registered, shall become the holder of record of such shares or Warrants as of the close of business on the Conversion Date.

(f) Upon the conversion of an interest in Global Notes, the Trustee (or other Conversion Agent appointed by the Company) shall make a notation on such Global Notes as to the reduction in the principal amount represented thereby. The Company shall notify the Trustee in writing of any conversions of Notes effected through any Conversion Agent other than the Trustee.

(g) If a Holder has submitted any Notes for purchase pursuant to Section 4.16, such Notes may be converted only if the Holder submits a withdrawal notice in accordance with Section 4.16(e) prior to the Change of Control Purchase Expiration Time.

(l) Clause (c) of Section 14.05 of the Indenture is hereby amended and restated in its entirety to read as follows:

(c) Upon conversion, Holders shall receive a separate cash payment or PIK Interest, as the case may be, for accrued and unpaid interest (including any Supplementary Interest, if any), to the Conversion Date, subject to Section 14.01(d) in the case of the Series A Notes, and to Section 14.04(e) in the case of the Series B Notes.

5

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

(b) Except for conversions upon a Fundamental Change as provided in Section 14.08, the Company shall deliver such cash and shares of Common Stock or Warrants, if applicable, on or before the third Business Day following the Conversion Date.

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

6

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

7

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

[Signature Page to Supplemental Indenture (Convertible Indenture)]

EXHIBIT A

EXHIBIT B