FIRST AMENDMENT TO MANAGEMENT AGREEMENT

Exhibit 10.5.1

FIRST AMENDMENT TO MANAGEMENT AGREEMENT

This FIRST AMENDMENT TO MANAGEMENT AGREEMENT dated as of September 7, 2005 (this “Amendment”), amending that certain Agreement, dated as of July 7, 2004 (the “Management Agreement”), is made and entered into by and among Castle Harlan, Inc., a Delaware corporation (“CHI”), Horizon Lines Holding Corp., a Delaware corporation (“Holdings I”), Horizon Lines, LLC (“Holdings II”), and Horizon Lines, Inc., a Delaware corporation formerly known as H-Lines Holding Corp. (“Holdings III”; and together with Holdings I and Holdings II, the “Companies”).

The parties hereto desire to amend the Management Agreement as herein provided.

NOW, THEREFORE, in consideration of the mutual agreements and covenants contained herein and for other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the undersigned hereby agree as follows:

1. Defined Terms. Capitalized terms used herein but not defined herein shall have the meanings ascribed to them in the Management Agreement.

2. Amendment of Section 2. Section 2 of the Management Agreement is hereby deleted in its entirety and replaced by the following:

“Term. The terms of Section 3, Section 4, and Sections 5(a) through (d) of this Agreement (the “Term”) shall expire upon the first to occur of (x) December 31, 2009 and (y) the receipt by CHI of a payment from the Companies to CHI pursuant to this clause (y) of cash in the aggregate amount of $7.5 million (the “Special Payment”); provided, that, notwithstanding the making by the Company of the Special Payment, the terms of Section 3, Section 4, Section 5(b), Section 5(c) and Section 5(d) of this Agreement shall be reinstated (a “Reinstatement”) automatically on January 1, 2006, if the firm, commitment underwritten public offering of shares of a class of common stock of Holdings III (an “Initial Public Offering”) has not been consummated, or at such earlier date that the Board of Directors of Holdings III abandons the Initial Public Offering. Upon a Reinstatement, the amount of the Special Payment will be applied, on a dollar-for-dollar basis, to the satisfaction of any amounts that shall be owed by the Companies to CHI from time to time on and after September 7, 2005 under Section 5(b)(ii) or Section 5(c) of the Agreement. Notwithstanding any other provisions contained in this Agreement to the contrary, the provisions of Section 5(e) and Sections 6 through 16 of this Agreement shall survive indefinitely.”

3. Amendment of Section 5(e). Section 5(e) of the Management Agreement is hereby deleted in its entirety and replaced by the following:

“In addition to the Initial Annual Fee and any Subsequent Annual Fee, the Companies shall, at the direction of CHI, pay directly or reimburse CHI for its Out-of-Pocket Expenses (as hereinafter defined) incurred in connection with (i) the Services provided for in Section 3 hereof and (ii) following the expiration of the term of Section 3 pursuant to Section 2 hereof, any services provided by CHI (or its affiliates) (whether before or after the Initial Public Offering) to the Companies and their direct and indirect subsidiaries (collectively, the “Special Services”). For purposes of this Agreement, the term “Out-of-Pocket Expenses” shall mean the reasonable amounts paid by CHI in connection with the Services provided for in Section 3 or the Special Services, including (x) fees and disbursements of any independent professionals and organizations, including independent auditors and outside legal counsel, investment bankers or other financial advisors or consultants, (y) costs of any outside services of independent contractors such as financial printers, couriers, business publications or similar services and (z) transportation, per diem, telephone calls, entertainment and all other reasonable expenses actually incurred by CHI in rendering the Services provided for herein or the Special Services. All reimbursements for Out-of-Pocket Expenses shall be made promptly upon or as soon as practicable after presentation by CHI to the Companies of a statement in connection therewith. The provision of any Special Services shall not be required of CHI (or its affiliates). No fees shall be payable to CHI in respect of such Special Services without the approval of the Board of Directors of Holdings III.”

4. No Other Amendments. Except as expressly provided in this Amendment, the Management Agreement remains in full force and effect in accordance with its terms.

5. Counterparts. This Amendment may be executed in any number of counterparts, each of which shall constitute an original instrument, but all of which when taken together shall constitute this Amendment.

6. Governing Law. This Agreement and the rights and obligations of the parties hereunder shall be governed by, and construed and interpreted in accordance with the internal laws of the State of New York.

7. Headings. The headings used herein are for convenience of reference only and shall not affect the construction of nor shall they be taken into consideration in interpreting, this Amendment.

8. Effectiveness. This Amendment shall become effective on the date when it is executed and delivered by each of the parties specified herein.

* * *

IN WITNESS WHEREOF, the parties hereto have caused this First Amendment to Management Agreement to be duly executed and delivered.