Exhibit 10.3

Execution Version

AMENDMENT TO CREDIT AGREEMENT AND ACKNOWLEDGEMENT

THIS AMENDMENT TO CREDIT AGREEMENT AND ACKNOWLEDGEMENT dated as of April 9, 2012 (this “Agreement”), is entered into among HORIZON LINES, INC., a Delaware corporation (“Parent”), HORIZON LINES, LLC, a Delaware limited liability company (the “Borrower”), the Lenders party hereto, and WELLS FARGO CAPITAL FINANCE, LLC, a Delaware limited liability company, as administrative agent for the Lenders (in such capacity, the “Agent”).

PRELIMINARY STATEMENTS

The Borrower, Parent, the Lenders and the Agent are parties to that certain Credit Agreement dated as of October 5, 2011 (as amended, restated, amended and restated, supplemented or otherwise modified from time to time, the “Credit Agreement”).

In connection with the Non-Domestic Reorganization and a restructuring of the obligations of the Borrower and Parent with respect to the Chartered Vessel Documents used in the Non-Domestic Service, (a) Parent and the Borrower have solicited the consent of the holders of the Secured Notes to certain amendments to the Secured Notes Documents, pursuant to the Consent Solicitation Statement relating to the Secured Notes (First Lien), the Consent Solicitation Statement relating to the Secured Notes (Second Lien) and the Consent Solicitation Statement relating to the Secured Notes (Convertible), each dated March 29, 2012 (collectively, the “Consent Solicitation Statements”), and (b) the Borrower intends to issue additional Secured Notes (Second Lien) in an aggregate principal amount not to exceed $40,000,000 (the “Additional 2012 Notes”).

The Borrower has requested that the Required Lenders agree to amend the Credit Agreement as more specifically set forth herein and to make the acknowledgement as more specifically set forth herein. Subject to the terms and conditions set forth herein, the Agent and the Required Lenders have agreed to such request of the Borrower.

NOW, THEREFORE, for good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties hereto hereby agree as follows:

1. Defined Terms. Except as otherwise provided herein, all capitalized undefined terms used in this Agreement (including, without limitation, in the introductory paragraph and the preliminary statements hereto) shall have the meanings assigned thereto in the Credit Agreement.

2. Amendments and Acknowledgement.

(a) New Definition. The following new definition is hereby added to Schedule 1.1 of the Credit Agreement in appropriate alphabetical order to read in its entirety as follows:

“Secured Notes Amendments” means the amendments dated on or before April 26, 2012 to the Secured Notes Documents described in the Consent Solicitation Statement relating to the Secured Notes (First Lien), the Consent Solicitation Statement relating to the Secured Notes (Second Lien) and the Consent Solicitation Statement relating to the Secured Notes (Convertible), each dated March 29, 2012.

(b) Permitted Indebtedness. Clause (p)(iv) of the definition of “Permitted Indebtedness” contained in Schedule 1.1 of the Credit Agreement is hereby amended by deleting therefrom the phrase “as in effect on the date hereof” and substituting therefor the phrase “as in effect on the date of the Secured Notes Amendments”.

(c) Permitted Additional Pari Passu Obligations. The definition of “Permitted Additional Pari Passu Obligations” contained in Schedule 1.1 of the Credit Agreement is hereby amended by deleting therefrom the phrase “as in effect on the Closing Date” and substituting therefor the phrase “as in effect on the date of the Secured Notes Amendments”.

(d) Change of Control. Certain holders of the Secured Notes have entered into restructuring support agreements (the “RSAs”) in connection with the Consent Solicitation Statements and the issuance of the Additional 2012 Notes. Notwithstanding the definition of “Change of Control” contained in Schedule 1.1 of the Credit Agreement, the Required Lenders acknowledge that the holders of the Secured Notes shall not be deemed to be acting as a “group” for purposes of such definition as a result of such holders entering into the RSAs for the period from the execution and delivery of the RSAs through the date of the Secured Notes Amendments.

3. Condition to Effectiveness. This Agreement shall be effective upon satisfaction of each of the following conditions (the date such conditions are satisfied, the “Agreement Effective Date”).

(a) Executed Amendment. The Agent’s receipt of counterparts of this Agreement executed by the Borrower, Parent, the Required Lenders and the Agent.

(b) Election to Convert. The holders of the Secured Notes (Convertible) shall have delivered to the Parent their irrevocable election to convert at least 95% of the total outstanding amount of the Secured Notes (Convertible) into Stock (other than Prohibited Preferred Stock) issued by Parent.

4. Condition Subsequent. The Loan Parties hereby agree that each of the following conditions shall be completed or satisfied on or before the dates set forth below (the failure by Borrower or Parent to so perform or cause to be performed such conditions subsequent as and when required by the terms thereof (unless such date is extended, in writing, by Agent, which Agent may do without obtaining the consent of the other members of the Lender Group), shall constitute an Event of Default):

(a) Conversion. Within 30 days after the Agreement Effective Date, the holders of the Secured Notes (Convertible) shall have converted at least 95% of the total outstanding amount of the Secured Notes (Convertible) into Stock (other than Prohibited Preferred Stock) issued by Parent.

(b) Executed Secured Notes Amendments. Within 30 days after the Agreement Effective Date, the Borrower shall have delivered to the Agent fully executed copies of the Secured Notes Amendments.

5. Effect of the Amendments and Acknowledgement. Except as expressly provided herein, the Credit Agreement and the other Loan Documents shall remain unmodified and in full force and effect. Except as expressly set forth herein, this Agreement shall not be deemed (a) to be a waiver of, or consent to, a modification of or amendment of, any other term or condition of the Credit Agreement or any other Loan Document, (b) to prejudice any other right or rights which the Agent or the Lenders may now have or may have in the future under or in connection with the Credit Agreement or the other Loan Documents or any of the instruments or agreements referred to therein, as the same may be amended, restated, amended and restated, supplemented or otherwise modified from time to time, (c) to be a commitment or any other undertaking or expression of any willingness to engage in any further discussion with the Borrower, Parent or any other Person with respect to any waiver, amendment, modification or any other change to the Credit Agreement or the Loan Documents or any rights or remedies arising in favor of the

2

Lenders or the Agent, or any of them, under or with respect to any such documents or (d) to be a waiver of, or consent to or a modification or amendment of, any other term or condition of any other agreement by and among any Loan Party, on the one hand, and the Agent or any other Lender, on the other hand. References in the Credit Agreement to “this Agreement” (and indirect references such as “hereunder”, “hereby”, “herein”, and “hereof”) and in any Loan Document to the Credit Agreement shall be deemed to be references to the Credit Agreement as modified hereby.

6. Representations and Warranties/No Default. By their execution hereof, each of the Borrower and Parent hereby represents and warrants as follows:

(a) Such Loan Party has the right, power and authority and has taken all necessary corporate and other action to authorize the execution, delivery and performance of this Agreement and each other document executed in connection herewith to which it is a party in accordance with their respective terms.

(b) This Agreement and each other document executed in connection herewith has been duly executed and delivered by its duly authorized officers, and each such document constitutes the legal, valid and binding obligation of such Loan Party, enforceable in accordance with its terms, except as such enforceability may be limited by bankruptcy, insolvency, reorganization, moratorium or similar state or federal debtor relief laws from time to time in effect which affect the enforcement of creditors’ rights in general and the availability of equitable remedies.

(c) Each of the representations and warranties set forth in the Credit Agreement and the other Loan Documents is true and correct in all material respects as of the date hereof (except to the extent that (i) any such representation or warranty that is qualified by materiality or by reference to Material Adverse Effect, in which case such representation or warranty is true and correct in all respects as of the date hereof or (ii) any such representation or warranty relates only to an earlier date, in which case such representation or warranty shall remain true and correct as of such earlier date).

(d) No Default or Event of Default has occurred or is continuing or would result after giving effect to the extension and the other transactions contemplated by this Agreement.

(e) No Additional Notes, Permitted Additional Pari Passu Obligations or Vessel Financing Debt has been issued or incurred prior to the date of this Agreement.

(f) Except as set forth in Schedule A hereto, there have been no amendments to, or modifications of, the Secured Notes prior to the date of this Agreement.

7. Reaffirmations. Each of Parent and the Borrower (a) agrees that the transactions contemplated by this Agreement shall not limit or diminish the obligations of such Person under, or release such Person from any obligations under, the Credit Agreement and each other Loan Document to which it is a party, (b) confirms, ratifies and reaffirms its obligations under the Credit Agreement and each other Loan Document to which it is a party, and (c) agrees that the Credit Agreement and each other Loan Document to which it is a party remain in full force and effect and are hereby ratified and confirmed.

8. Release of Claims. To induce the Agent and the Lenders to enter into this Agreement, Borrower and Parent each hereby releases, acquits and discharges the Agent and the Lenders, and all officers, directors, agents, employees, successors and assigns of the Agent or any Lender, from any and all liabilities, claims, demands, actions or causes of action of any kind or nature (if there be any), whether absolute or contingent, disputed or undisputed, at law or in equity, known or unknown, that the Borrower

3

or Parent now has or ever had against the Agent or any Lender arising under or in connection with any of the Loan Documents or otherwise. Each of the Borrower and Parent represents and warrants to the Agent and the Lenders that neither the Borrower nor Parent has not transferred or assigned to any Person any claim that such Loan Party ever had or claimed to have against the Agent or any Lender.

9. Miscellaneous

(a) Governing Law. THIS AGREEMENT SHALL BE GOVERNED BY, AND CONSTRUED IN ACCORDANCE WITH, THE LAW OF THE STATE OF NEW YORK. Without limiting the general applicability of the foregoing and the terms of the other Loan Documents to this Agreement and the parties hereto, the terms of Section 12 of the Credit Agreement are incorporated herein by reference, mutatis mutandis.

(b) Loan Document. This Agreement shall constitute a “Loan Document” under and as defined in the Credit Agreement.

(c) Counterparts; Electronic Execution. This Agreement may be executed in counterparts (and by different parties hereto in different counterparts), each of which shall constitute an original, but all of which when taken together shall constitute a single contract. Delivery of an executed counterpart of a signature page of this Agreement by telecopy or other electronic imaging means shall be effective as delivery of a manually executed counterpart of this Agreement

(d) Severability. If any provision of any of this Agreement is determined to be illegal, invalid or unenforceable, such provision shall be fully severable and the remaining provisions shall remain in full force and effect and shall be construed without giving effect to the illegal, invalid or unenforceable provisions.

(e) Entirety. This Agreement, the other Loan Documents and the other documents relating to the Obligations represent the entire agreement of the parties hereto and thereto, and supersede all prior agreements and understandings, oral or written, if any, including any commitment letters or correspondence relating to the Loan Documents, any other documents relating to the Obligations, or the transactions contemplated herein and therein.

[Remainder of page intentionally blank.]

4

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

Horizon Lines

Amendment to Credit Agreement

and Acknowledgement

Horizon Lines

Amendment to Credit Agreement

and Acknowledgement

SCHEDULE A

TO AMENDMENT TO CREDIT AGREEMENT

AND ACKNOWLEDGEMENT

Amendments and Modifications to Secured Notes