AMENDMENT NO. 3 TO AMENDED AND RESTATED CREDIT AGREEMENT

Exhibit 10.40

AMENDMENT NO. 3

TO

AMENDED AND RESTATED

CREDIT AGREEMENT

This AMENDMENT NO. 3 to the AMENDED AND RESTATED CREDIT AGREEMENT, dated as of December 12, 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 through the date hereof 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.

WITNESSETH:

WHEREAS, the Borrower has requested that the 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: ““Amendment No. 3. Effective Date” shall mean the date that Amendment No. 3 to this Agreement shall become effective in accordance with its terms.”

(b) The definition of “Excess Cash Flow” in Section 1.01 of the Credit Agreement shall be amended by adding to clause (f) of such definition, immediately after the word “period” appears in such clause (f), the following; “(other than prepayments or repayments of any Loans pursuant to Section 2.11(a))”.

(c) The following sentences shall be added at the end of the definition of “Revolving Commitment” in Section 1.01 of the Credit Agreement: “Following the Amendment No. 3 Effective Date, the amount of each Lender’s Revolving Commitment shall be set forth on

Schedule 2.01 or in the Assignment and Assumption pursuant to which such Lender shall have assumed its Revolving Commitment, as applicable. The initial aggregate amount of the Lenders’ Revolving Commitments from and after the Amendment No. 3 Effective Date shall be $75,000,000.”

(d) Section 2.02(d)(w) of the Credit Agreement is hereby amended by replacing the reference to “$50,000,000” therein with “$75,000,000”.

(e) Section 2.11(d) of the Credit Agreement is hereby amended by (i) replacing the reference to “2006” therein with “2007” and (ii) adding, immediately after the words “Excess Cash Flow for such fiscal year” appear in such Section 2.11(d), the following “minus 100% of the aggregate amount of Tranche C Loans prepaid during such fiscal year pursuant to Section 2.11(a) and, to the extent there is an equivalent reduction in the Revolving Commitments made simultaneously with such prepayment, 100% of the Revolving Loans prepaid during such fiscal year pursuant to Section 2.11(a)”.

(f) Section 6.04(i) of the Credit Agreement is hereby amended by replacing the reference to (x) “$30,000,000” therein to “$120,000,000” and (y) “$100,000,000” therein to “$200,000,000”.

(g) Section 6.08(a)(xi) of the Credit Agreement is hereby amended by replacing the reference to “$15,000,000” therein to “$36,000,000”.

(h) Section 6.14 of the Credit Agreement is hereby amended by (x) replacing clause (a) of such Section 6.14 thereof in its entirety with the following: “(a) expenditures used to acquire shipping containers, chassis, gensets, cranes, container handling equipment, over-the-road and yard tractors, other yard and terminal vehicles and equipment or other related Vessel assets which were, immediately prior to such purchase, leased or subleased by Holdings or any of its subsidiaries shall, solely for the purposes of this Section 6.14, be deemed not to be Capital Expenditures for such fiscal year; provided that the amount of such expenditures made pursuant to this clause (a) shall not exceed (x) $15,000,000 in the aggregate in any fiscal year (except that to the extent that $15,000,000 exceeds the aggregate expenditures made pursuant to this clause (a) in such fiscal year, such excess may be carried over and used for such expenditures in the fiscal year following such fiscal year, so long as the limitation in the immediately succeeding clause (y) shall not be violated by such carry-over) or (y) $40,000,000 in the aggregate during the term of this Agreement,” (y) in clause (b) of such Section 6.14 thereof, deleting the words “50.00% of” and (z) the numbers in the right column of the chart at the end of such Section 6.14 opposite the years 2006, 2007, 2008, 2009, 2010 and 2011 shall all be deemed deleted and replaced with “$40,000,000”.

(i) Schedule 2.01 shall be amended to reflect the increased Revolving Commitments as of the Amendment No. 3 Effective Date.

SECTION TWO     Conditions to Effectiveness. This Amendment shall become effective as of the date (the “Amendment No. 3 Effective Date”) if 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 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. 3 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. 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).

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]