AMENDMENT NO. 2 TO AMENDED AND RESTATED CREDIT AGREEMENT

Exhibit 10.5

AMENDMENT NO. 2

TO

AMENDED AND RESTATED

CREDIT AGREEMENT

This AMENDMENT NO. 2 to the AMENDED AND RESTATED CREDIT AGREEMENT, dated as of April 7, 2006 (this “Amendment”), is entered into among HORIZON LINES, LLC, a Delaware limited liability company (the “Borrower”), UBS AG, STAMFORD BRANCH, as administrative agent (in such capacity, the “Administrative Agent”), UBS AG, STAMFORD BRANCH, as Issuing Bank (in such capacity, the “Issuing Bank”) and the Lenders party hereto, and amends the Amended and Restated Credit Agreement dated as of April 7, 2005 (as amended by Amendment No. 1 thereto, dated as of September 22, 2005, and as may be further amended, supplemented or otherwise modified from time to time, the “Credit Agreement”) entered into among the Borrower, the institutions from time to time party thereto as lenders, UBS AG, Stamford Branch, as administrative agent (in such capacity, the “Administrative Agent”), HORIZON LINES HOLDING CORP., a Delaware corporation (the “Co-Borrower”), and the other parties thereto. Capitalized terms used herein and not otherwise defined herein shall have the meanings ascribed to them in the Credit Agreement.

W I T N E S S E T H:

WHEREAS, the Borrower has requested that the Required Lenders and the Administrative Agent amend the Credit Agreement to effect the changes described below in Section One;

WHEREAS, Section 9.02 of the Credit Agreement provides that the Credit Agreement may be amended, modified and waived from time to time;

NOW, THEREFORE, in consideration of the premises and for other good and valuable consideration (the receipt and sufficiency of which is hereby acknowledged), the parties hereto hereby agree as follows:

SECTION ONE Amendments.

(a) The following definitions shall be added to Section 1.01 of the Credit Agreement:

(i) “Amendment No. 2. Effective Date” shall mean the date that Amendment No. 2 to this Agreement shall become effective in accordance with its terms.”

(ii) “April 2006 SFL Documents” shall mean the collective reference to the shipbuilding agreements, purchase agreements, memorandum of agreements, reimbursement agreements, indemnity agreements, agreements to acquire and charter, bareboat agreements, credit agreements and other agreements, instruments and documents, each dated as of the Amendment No. 2 Effective Date, pursuant to which SFL shall purchase five Vessels and then

lease and/or charter such Vessels to Holdings or one or more of its subsidiaries, in each case as any one or more of such agreements may be amended, modified or otherwise changed following the Amendment No. 2 Effective Date in any manner that could not reasonably be expected to materially and adversely affect the interests of the Lenders or as otherwise may be agreed to by the Administrative Agent.”

(iii) “SFL” shall mean Ship Finance International, Ltd and/or any of its subsidiaries or Affiliates.

(b) The reference to “$20,000,000” in Section 2.05(b) of the Credit Agreement is hereby changed to “$41,000,000”.

(c) The following shall be inserted at the end of the third sentence of Section 3.10(c): “; provided that neither the Chartered Vessels chartered pursuant to the April 2006 SFL Documents nor the owners of such Chartered Vessels shall be required to be qualified to operate in the coastwise trade of the United States.”

(d) The word “and” at the end of clause (xxiii) of Section 6.01 shall be deleted.

(e) The period at the end of clause (xxiv) of Section 6.01 shall be replaced with “; and”.

(f) The following new clause (xxv) shall be added at the end of Section 6.01: “(xxv) any Guarantees (whether in the form of a reimbursement, indemnity or otherwise) of Holdings or any of its subsidiaries of any obligations of SFL in connection with one or more deposits or other obligations in respect of the purchase of Vessels by SFL pursuant to the April 2006 SFL Documents, including the issuance of any Letters of Credit (and any drawing thereon) for the benefit of SFL or any other Person, including any lender of SFL, to support any of such Guarantees, so long as the aggregate amount of all such Guarantees (and the aggregate face amount of all Letters of Credit provided in connection therewith) does not exceed $42.5 million.”

(g) The period at the end of the proviso to clause (s) of Section 6.04 shall be replaced with “; and”.

(h) The following new clause (t) shall be added to the end of Section 6.04: “(t) any Guarantee (whether in the form of a reimbursement, indemnity or otherwise) permitted by, or described under, Section 6.01(xxv), including any Letters of Credit (and any drawing thereon) provided to SFL or any lender or financing provider of SFL to support such Guarantee.”

SECTION TWO Conditions to Effectiveness. This Amendment shall become effective as of the date (the “Amendment No. 2 Effective Date”) if, at or prior to 5:00 p.m. on April 5, 2006 (such date and time, the “Deadline”), the Administrative Agent shall have received counterparts of this Amendment executed by (i) the Borrower, (ii) UBS AG, Stamford Branch, in its capacity as Issuing Bank and as Administrative Agent and (iii) fully executed Confidential Lender Authorizations (as defined below) from a number of Lenders sufficient to constitute

the Required Lenders. The effectiveness of this Amendment (other than Sections Five, Six and Eight hereof) is conditioned upon the accuracy of the representations and warranties set forth in Section Three hereof.

SECTION THREE Representations and Warranties. In order to induce the Lenders party hereto and the Issuing Bank to enter into this Amendment, the Borrower represents and warrants to each of the Lenders that both before and after giving effect to this Amendment: (a) no Default or Event of Default has occurred and is continuing and (b) all of the representations and warranties in the Credit Agreement are true and complete in all material respects on and as of the date hereof as if made on the date hereof (or, if any such representation or warranty is expressly stated to have been made as of a specific date, as of such specific date).

SECTION FOUR Reference to and Effect on the Credit Agreement. On and after the Amendment No. 2 Effective Date, each reference in the Credit Agreement to “this Agreement,” “hereunder,” “hereof” or words of like import referring the Credit Agreement, and each reference in each of the Loan Documents to “the Credit Agreement,” “thereunder,” “thereof” or words of like import referring to the Credit Agreement, shall mean and be a reference to the Credit Agreement, as further amended by this Amendment. The Credit Agreement and each of the other Loan Documents, as specifically amended by this Amendment, are and shall continue to be in full force and effect and are hereby in all respects ratified and confirmed. The execution, delivery and effectiveness of this Amendment shall not, except as expressly provided herein, operate as a waiver of any right, power or remedy of any Lender or any Agent under any of the Loan Documents, nor constitute a waiver of any provision of any of the Loan Documents.

SECTION FIVE Costs and Expenses; Amendment Fee. Borrower agrees to pay all reasonable costs and expenses of the Administrative Agent in connection with the preparation, execution and delivery of this Amendment and the other instruments and documents to be delivered hereunder, if any (including, without limitation, the reasonable fees and expenses of Cahill Gordon & Reindel LLP, counsel to the Administrative Agent). Promptly (but in any event not later than one Business Day) following the Amendment No. 2 Effective Date, the Borrower hereby covenants and agrees that it shall, in immediately available funds through the Administrative Agent, pay to each (i) Tranche C Lender that delivers a Confidential Lender Authorization at or prior to the Deadline a fee equal to 0.10% of the aggregate principal amount of Tranche C Term Loans held by such Tranche C Lender as of the Amendment No. 2 Effective Date and (ii) Revolving Lender that delivers a Confidential Lender Authorization at or prior to the Deadline a fee equal to 0.10% of the aggregate principal amount of Revolving Commitments and Revolving Exposure of such Revolving Lender as of the Amendment No. 2 Effective Date; provided that no fees referred to in this sentence shall be payable if the Amendment No. 2 Effective Date shall not occur. If the foregoing sentence shall not be complied with, it is agreed that this Amendment shall be void and of no further force or effect.

SECTION SIX Execution in Counterparts. This Amendment may be executed in any number of counterparts and by different parties hereto in separate counterparts, each of which when so executed shall be deemed to be an original and all of which taken together shall constitute but one and the same agreement. Delivery of an executed counterpart of a signature page to this Amendment by telecopier or electronic mail shall be effective as delivery of a manually executed counterpart of this Amendment.

SECTION SEVEN Confidential Lender Authorizations. “Confidential Lender Authorizations” are the confidential lender authorizations in the form distributed to each of the Lenders in connection with this Amendment. Each Lender that signs a Confidential Lender Authorization shall be deemed to have approved this Amendment and shall be further deemed for the purposes of the Loan Documents to have approved this Amendment. Each Lender signatory to a Confidential Lender Authorization agrees that such Lender shall not be entitled to receive a copy of any other Lender’s Confidential Lender Authorization, but agrees that a copy of such Confidential Lender Authorization may be delivered to Borrower.

SECTION EIGHT Governing Law. THIS AMENDMENT SHALL BE GOVERNED BY, AND CONSTRUED IN ACCORDANCE WITH, THE LAWS OF THE STATE OF NEW YORK.

[Signature Pages Follow]